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

Answer 2

Following combination will generate unique binary tree(which can be BST).

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

So in your case inorder & pre order are given which will generate unique binary tree which is BST in your case so level order will be unique for that tree.

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

SO tree will be

level 0- 4
level 1- 1,5
level 2- 2,6
level 3- 3,7
level 4- 8

Level order is

4,1,5,2,6,3,7,8

in sort there will always unique level order traversal