# Level order sorted binary tree from a binary tree

Lets suppose we have a binary tree . Tree node structure is as

struct node
{
int val ;
struct node *left , *right ;
}

Now we have to sort the tree in level order manner . For example lets suppose we have original tree like this

root = 6
root->left = 1
root->right = 9
root->left->left = 8
root->right->right = 2

Then after applying level order sorting , our tree will be

root = 1
root->left = 2
root->right = 6
root->left->left = 8
root->right->right = 9

One way of doing this problem is just take all the values in a array and apply any of the standard sorting algorithm and then put back the values in tree in level order traversal manner. This solution is not efficient in term of space and time both.

What algorithm can I use to decrease operations and memory usage from my proposed plan? Is there a more efficient algorithm to do this without the use of a sorted array?

Level order sorting :
Level order sorting means if you do level order traversal of the tree then you should get a sorted non-decreasing sequence .

Constraint :
Shape of the tree should not alter that is if in original tree left child of the root does not have right child (as in my example) then after sorting too, it should not has right child .

Sounds like you need a type of heap with some modified properties. First, use a min-heap instead of a max-heap: every node is less than the values of its children, and add a constraint that a node is greater than its siblings to the left.

One of the neat features of a heap is that it is a balanced binary tree: the depth of all leaf nodes vary by at most 1. Furthermore, leaf nodes are populated left to right. While this is not quite the same representation as you have, it makes the whole thing a ton easier.

If you take a tree with these properties and perform a level-order traversal, you can easily convert it to and from an array:

root = 6
root->left = 1
root->right = 9
root->left->left = 8
root->left->right = 2

Level-order traversal gives the following: 6, 1, 9, 8, 2.

Note how each level takes 2^n elements in that array, where n is the depth of the nodes at that level. The root node has depth 0, so it takes 2^0 = 1 element. Next level has depth 1, so it takes 2^1 = 2 elements. This property means there is a direct correlation between a specific element in the tree and its array position.

Now perform an efficient sort on that array, and you get: 1, 2, 6, 8, 9.

Perform the reverse of the first transformation. Element 0 is the root, Elements 1 and 2 are the next level, elements 3, 4, (and 5, 6 if present) are the next level.

root = 1
root->left = 2
root->right = 6
root->left->left = 8
root->left->right = 9

If you need to maintain the fact that leaves are not populated left to right, or the tree is not balanced, you can add gaps by saying certain nodes are null and modify a sort algorithm to leave null values in-place. Not ideal, but it can allow you to leverage the properties of a heap to do this. Level-order sorting pretty much has to be done using a heap as far as I am aware (made it through a B.S. and M.S. in computer science without ever hearing or seeing another way to do this, and you know the real world doesn't care).

• Please check your in-order traversal , is it correct ? Aug 13, 2014 at 8:12
• Looks right to me: do you notice anything specific that may be incorrect?
– user22815
Aug 13, 2014 at 14:15
• ya in my knowledge it should be 8,1,2,6,9 Aug 14, 2014 at 16:47
• I used the wrong terminology. I said "in-order" while describing "level-order" which also matches the heap structure. I went back and fixed my answer.
– user22815
Aug 14, 2014 at 16:51
• thank u ! and don't forget to come back on this question if u get a another solution to share with us . Thank u for your response. Aug 14, 2014 at 16:52

Assume that you have a forward-only iterator that will visit the tree in level order, this can be accomplished using an insertion-style sort, two iterators and one location of temporary storage.

For each node (using Iterator1)
Put the value into temp
For each node up to Iterator1 (using Iterator2)
Skip until temp >= value
Insert temp and move values down one position

Very efficient in space, not so much in speed but easy to code.

If there is enough space to copy all the values, then there is a faster algorithm by copying them out, sorting them and copying them back in again.

By way of clarification, a 'forward only iterator' means a pointer or index or other mechanism that allows every node to be visited in a pre-defined order, but does not allow reversing or random access. This is the commonest way to traverse trees, and probably what you're already doing.

With two of these and a single temporary you can implement an in-place sort. The first (outer) iterator does a single pass from start to end and taking out one value each time. The second (inner) does multiple passes from beginning to outer iterator, first finding where to put the value that was removed, and then shuffling the remaining values down. That's an insertion sort (but quite similar to a bubble sort). It's probably 5-10 lines of code, depending on language.

• I am not getting your algorithm . Can you explain the term "forward-only iterator" and how this "forward only iteration " traverse the tree ? Aug 14, 2014 at 16:50
• @sdream I think his idea is basically the equivalence of: [1] Having a visitor that visits each node BFS style. [2] Keep a tmp value that holds the lowest value that has been seen [3] Find the min value in the tree that is greater than tmp [4] swap the min value with the value currently has in the visitor's node [5] move the visitor to next node [6] update the tmp value [7] repeat finding new min value that is greater than new tmp, don't forget to skip over nodes already visited by BFS visitor. Aug 14, 2014 at 17:26
• @sdream: See edit. Aug 15, 2014 at 5:54
• @randomA: Right idea, wrong algorithm. See edit. But yours might work too. Aug 15, 2014 at 5:55
• @randomA: What you described is a Selection sort. Simple and often good enough, but Insertion sort is usually faster. Aug 16, 2014 at 7:34