Sorting the elements in Binary trees

Question

Here is a question I was recently asked in an interview. A binary tree is given with a condition that each left child is 1 smaller than root and right child is 1 larger. Here is a sample tree

Sort it in O(1) and O(n) time complexity.

Here are the approaches I suggested:

1. Use a count to maintain the count of each elements and then return once entire traversal is done O(n) time and O(n) space complexity.
2. Use run length encoding. Form a chain when the element is repeated with the number as the key and count as the value. Requires space for count only when no is repeated and so requires no extra space apart from array but the time complexity will be O(n log n) since we have to traverse the array to see if it is there.
3. Finally I suggested breadth first traversal. We require O(log n) space for queue and O(n) time complexity (Assuming insertion is O(1) linked list).

What are your approaches?

Solution 1

Fix some Leaf node of the given tree as NewHead .

Write a function Pop() remove some node from the given tree ..!

Write pop node such that you will remove it only when it is ! equal to NewHead .

So pop value from tree , insert it to the New binary search tree with New Head as Head node .

So u will remove an element from tree add it to new search tree .

Until tree head point NewHead .

So all you elements are now in binary search tree pointing to the New head , which will be

obviously in sorted order .

This way promise you a sorting in O(NlogN) .

Solution 2

Analysis

Given your definition of a binary-tree we have the following,

Each Node have a Parent, L-child, and R-child .. where:

L < N

R > N

P > N

We also can do this:

L < N AND R > N => L < N < R => L < R

L < N AND P > N => L < N < P => L < P

R > N AND P > N => N < MIN(P,R)

N < MIN(P,R) AND L < N => L < N < MIN(P,R)

And now let's try expanding it, N.L = Left-child of N:

N.L < N
N.R > N
N.P > N

N.L.L < N.L < MIN(N, N.L.R)
N.L.R > N.L > N.L.L

N.R.L < N.R < MIN(N, N.R.R)
N.R.R > N.R > N.R.L

IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R)

IF N IS N.P RIGHT-CHILD: N > N.P.R

---

Proposed Solution

This problem seems complex, but my solution will be using merge sort after inserting values in a traversal order Left-Right-Parent which will help the merge sort to get a time complexity somewhere between its average and optimal case, but with a small trick using the comparisons I've done above.

First we collect tree nodes in a list, using Left-Right-Parent traversal, given the fact that: N.L < N < MIN(N.R, N.P) and with giving the parent a higher weight assuming O(N.R) <= O(N.P) with values decrease linearly when we go left-side each time .. > N.R.R > N.R > N > N.L > N.L.L > ...

After collecting the tree nodes in that traversal order, the list have some sorted chunks, which will help the merge sort that we'll use next.

This solution works in: Time = O(n log n + n), Space = O(n)

Here is the algorithm written in Java (not tested):

private class Node Comparable<Node>
{
    public Node R;
    public Node L;
    public int value;

    public Node (Node L, int val, Node R)
    {
        this.L = L;
        this.value = val;
        this.R = R;
    }

    @Override
    public int compareTo(Node other)
    {
        return ((other != null) ? (this.value-other.value) : 0);
    }
}

class Main
{
    private static Node head;

    private static void recursive_collect (Node n, ArrayList<Node> list)
    {
        if (n == null) return;
        if (n.left != null) recursive_collect (n.L, list);
        if (n.right != null) recursive_collect (n.R, list);
        list.add(n.value);
    }

    public static ArrayList<Node> collect ()
    {
        ArrayList<Node> list = new ArrayList<Node>();
        recursive_collect (head, list);
        return list;
    }

    // sorting the tree: O(n log n + n)
    public static ArrayList<Node> sortTree ()
    {
        // Collecting nodes: O(n)
        ArrayList<Node> list = collect();

        // Merge Sort: O(n log n)
        Collections.sort(list);

        return list;
    }

    // The example in the picture you provided
    public static void createTestTree ()
    {
        Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null));

        Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null));

        Node right = new Node (left2, 1, new Node(null,2,null));

        head = new Node (left1, 0, right);
    }

    // test
    public static void main(String [] args)
    {
        createTestTree ();

        ArrayList<Node> list = sortTree ();

        for (Node n : list)
        {
            System.out.println(n.value);
        }
    }
}

Solution 3

I guess , you are looking for DFS(depth first search). In depth-first search the idea is to travel as deep as possible from neighbour to neighbour before backtracking. What determines how deep is possible is that you must follow edges, and you don't visit any vertex twice.

boost already provides it: see here

Comments

[MissingNumber]

No the numbers are are not in sorted order.! You need sort them and change the position of numbers..!!

[JackSparrow]

@Jessica you are getting confused between "binary search tree" and "binary tree". The question explicitly state that "sorting in binary trees" and the code you mentioned is Inorder traversal of BST which is not the case here.

[Harshit Bangar]

This one seems to be a better solution. Doing depth first traversal but with moving directly to the node from queue is one solution. Using it along with list (o(1) insertion) will give o(n) solution with space complexity of o(h).