0

We can construct unique binary search tree using say pre order traversal output as follows:

  1. First element will be the root.
  2. Left child = nearest element less than the root.
  3. Right child = nearest element greater than the root.

These facts are very easy to convert to the code. However I am struggling to get such rigid facts/steps to convert level order traversal output to unique binary search tree.

For example if I have following level order traversal output [5,4,8,1,7,2,6,3], I can form BST as follows:

      5
    /   \
   4     8
  /      /
 1      7
  \    / 
   2  6
    \
     3 

The first element in level-order traversal is always the root (level 0). Then comes is elements at level 1. 4 is less than 5, so I will put it as left child pf 5. 8 is greater than 5, so I will put it as right child of 5. (It cannot be child of 4, since in that case it should be lesser than 5. Thus it cannot appear at level 2). Then comes 1 and 7. 1 should be left child of 4 as it is less than 4. 7 cannot be right child of 4, as it is greater than 5 also. So it should be on right subtree of 5. Thus it has to be left child of 8, as 7 < 8. We can continue the same for all.

What I feel is that this turns out to be the normal BST creation. That is, it is creating BST by inserting nodes in empty BST in the sequence of level order output. Is it? I mean are there steps equivalent to the ones above as in case of constructing unique BST from pre order traversal output. Or we just have to follow BST creation algorithm and insert nodes in empty BST in the sequence of level order traversal output?

1 Answer 1

2

Or we just have to follow BST creation algorithm and insert nodes in empty BST in the sequence of level order traversal output?

This can be done much more efficiently (linear time vs. Θ(n log(n))), but it needs to be done with care. In your verbal description , the question of when to move to a new node in a parent level, needs to be made more precise.

Suppose that as you construct the tree, then for each node v, you store an auxiliary variable c(v) which is the cutoff value beyond which an item cannot be a child of v.

  • When you start, you construct the node 5 with c(5) = ∞ (because only if something is larger than will it not be a child of this node).

  • The next item is 1. Since 4 < c(5) = ∞, then 1 can be a child of 5; since it is smaller, it must be the left child. Since it is a left child, its cutoff is the value of the parent, so c(4) = 5.

  • The next item is 8. Again, 8 < c(5) = ∞, so it can be a child, but it must be the right child. Since it is the right child, its cutoff is the cutoff of its parent, so c(8) = ∞.

  • Similarly, 1 becomes the child of 4 and takes its cutoff level as 4.

  • 7 cannot be a child of 4. It is greater than the cutoff level for 4. We move on to the next node at the previous level, which is 8. It can indeed be a child of 8, and becomes its left child, taking 8 as its own cutoff level.

Continue as above:

  • Each node can be a child of a node in the previous level, if it is beneath the cutoff of the node in the previous level. If not, move on to the next node in the previous level as a candidate.

  • For the first node in the previous level for which the new node is less than the cutoff:

    • If it is less than the node, it becomes a left child, and takes the value of the parent node as its cutoff.

    • If it is greater than the node, it becomes a right child, and takes the cutoff of the parent as its own cutoff.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.