Binary tree from in-order and level-order traversals?

Question

Can we prove that one can unambiguously construct a binary tree from its in-order and level-order traversals?

I am thinking of a proof by induction on number of levels.

Base case: trees with 1 or 2 levels. These cases are clear.

Assume that this holds for trees with l levels. That is: one can unambiguously construct a binary tree with l levels from its in-order and level-order traversals.

Inductive case: prove that this holds for trees with l+1 levels. Not clear how to proceed in this case. Any help will be appreciated.

Answer 1

I have given this tutorial on my blog a) - INORDER Traversal -POSTORDER Traversal

OR

b) -INORDER Traversal -PREORDER Traversal

We usually get Questions like :-

Create Binery tree from following tree Traversals

1)

Inorder:   E  A  C  K  F  H  D  B  G
Preorder:  F  A  E  K  C  D  H  G  B

HERE the most important think to ALWAYS remember is :-

In PREorder FIRST element is ROOT of the tree

In POSTorder LAST element is ROOT of the tree

I hope you got it :P

i.e considering 1) Question

1) Inorder: E A C K F H D B G Preorder: F A E K C D H G B

F is root

E A C K will go to LEFT SUB TREE of Root

H D B G will go to RIGHT SUB TREE of Root

Step 1)

Now as we know which one is Root So...

                     F
                   /  \
        ( E A C K)      (H D B G) 


Step 2)

Now FOR LEFT SUB TREE we have E A C K from Inorder and same letters A E K C from Preorder

i.e

 Inorder   E A C K
 Preorder A E K C

now have found A as Root again so now tree is

                     F
                   /   \
                  A      (H D B G) 
                /  \
               E    (C K)


Step 3)

Now letters are

Inorder   C K
Preorder  K C

So now tree is

                           F
                         /   \
                        A     (H D B G) 
                      /  \
                     E    K
                         /
                        C

Same procedure can be done on Right Sub tree Of root F

For Postorder we have to find Root as the last element in traversal....

Colorfull version or this can be seen here http://bloggerplugnplay.blogspot.in/2012/11/construction-of-binary-tree-from.html :P

Answer 2

Not sure about proof, but the alg for doing so would be along the lines,

f(inorder, levelorder):
      if length(levelorder) == 0:
          return None
      root = levelorder[0]#set root to first element in levelorder
      subIn1, subIn2 = partition(inorder, levelorder[0]) #partition inorder based on root
      subLevel1 = extract(levelOrder, subIn1)#remove elements in level order not in subIn1
      subLevel2 = extract(levelOrder, subIn2)#remove elements in level order not in subIn2
      root->left = f(subIn1, subLevel1)
      root->right = f(subIn2, subLevel2)
      return root

To prove it you would have to show that the sequence left of a root node in an inorder traversal is an inorder traversal of the left subtree, and then the same for the right. True, but tedious to prove.

You would also need to show that levelorder is maintained for subtrees. Also true, but tedious to prove.

Oh yeah, you may have to prove that the first element in a level order traversal is the root of a tree, but that should come from the definition.