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?

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