Take the 2-minute tour ×

Here is a question I recently have for my 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 http://postimg.org/image/a76lcv16r/ (direct link - http://s21.postimg.org/wj4e690av/Drawing1.jpg)

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*logn) since we have to traverse the array to see if it is there.
  3. Finally I suggested breadth first traversal. We require o(logn) space for queue and o(n) time complexity (Assuming insertion is o(1) linked list).

What are your approaches.

share|improve this question
What do you mean by 'O(1) and O(n) time complexity'? Do you mean O(1) space? I can imagine that there is an O(n) algorithm by balancing the tree in a similar way to AVL trees and then doing an inorder traversal. –  Andrew Mao Mar 29 '13 at 4:45
What does sort exactly mean? The method needs to returns a sorted list? printf? Can we modify the tree? –  Knoothe Mar 29 '13 at 22:11
Is the O(1) space a real requirement? Just doing any traversal seems hard (if we can't modify the tree) to do in O(1) space. Perhaps it was O(height)? btw, bfs takes Omega(n) space. Not O(log n). –  Knoothe Mar 29 '13 at 22:20
o(1) space as a strict requirement. Take your point on BFS it is Omega(n). It was mentioned that you should not use any extra space and do it in o(n) time . Between the idea on O(height). Sort means to return a sorted list. –  user2223032 Mar 30 '13 at 0:36
how can you build a length-n list in o(1) space? Do you mean you need that we need to destroy the tree to make room? –  mitchus Apr 7 '13 at 18:49
add comment

5 Answers


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



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;

    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);

    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)

        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)
share|improve this answer
add comment

I'm not getting the question. Aren't binary trees already sorted? If you'd like to print out the items in order (or access them in order), this code would work

* Show the contents of the BST in order
public void show () {
private static void show(TreeNode node) {
if (node == null) return;
System.out.print(node.datum + " ");

I believe this would be o(n) complexity. To return a list instead of printing, just create one and replace each show statement by adding the child to the list

share|improve this answer
No the numbers are are not in sorted order.! You need sort them and change the position of numbers..!! –  MissingNumber Mar 29 '13 at 16:31
@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. –  JackSparrow Mar 30 '13 at 9:10
add comment

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) .

share|improve this answer
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). –  user2223032 Apr 7 '13 at 14:04
add comment

Use quick sort.

The nodes are sorted at lowermost level in multiple arrays & these arrays of sorted elements are merged i the end.


Function quick_sort(node n)
1. Go to left mode, if is not null, call quick_sort on it.
2. Go to right elements, if is not null, call quick_sort on it.
3. Merge results of left node sort & right node sort & current node.
4. Return merged array.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


