How many level order BST sequences are possible given a preOrder and inOrder sequence?

Question

When I am trying to print level Order of BST, this question prompted me.

Here is a

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8

A level order sequence for a BST with above pre_order and In_order is [4, 2, 6, 1, 3, 5, 7, 8]

However, for the same Pre-order an In-order sequence this level order sequence seems possible. [4, 1, 5, 2, 6, 3, 7, 8]. I don't know how. I am trying to figure this out.

I am unable to construct BST in paper (drawing) that satisfies all the pre_order, In-order and level order sequences.

Answer 1

If you have in-order traversal together with one of pre/post-order, that is enough to reconstruct a binary tree. Moreover, in case of BST (binary search tree), post-order or pre-order alone is sufficient.

In your case, reconstructing a BST from pre-order 4, 1, 2, 3, 5, 6, 7, 8 gives the following BST:

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

which gives, again unique, level-order traversal [4,1,5,2,6,3,7,8].

See also:

• Reconstructing binary trees from tree traversals