Interra Systems

Q1.  Given the pre-order and in-order traversal of a Binary Tree, find out the structure of the Tree.
        pre-order : 10, 5, 4, 3, 6, 20, 15, 14, 16, 25, 30
        in-order   :  3, 4, 5, 6, 10, 14, 15, 16, 20, 25, 30

Solution:

Algorithm:
In pre-order Traversal of a Binary Tree, we visit the root node first, then left node, and finally right node.
So, in pre-order traversal, root node is printed first.
Here, 1st element in pre-order is 10.

=> Root Node = 10.

Now, we know that in in-order traversal of a BT, left sub-Tree is printed first, followed by Root and then Right sub-Tree.
So, all elements to the left of 10(Root), lie in the left sub-tree, and all elements to the right of 10 lie in right sub-tree.

in-order : 3, 4, 5, 6, [10], 14, 15, 16, 20, 25, 30
=> Root = 10
      Left sub-tree (T1)   = {3, 4, 5, 6}
      Right sub-tree (T2) = {14, 15, 16, 20, 25, 30}

So, we have broken the problem into 2 small sub-problems. If we can find the structure of T1 and T2, we can get the structure of entire tree.
T = (T1) Root (T2)
                                      [10]
                                   /         \
                                 /             \
                    (3, 4, 5, 6)     (14, 15, 16, 20, 25, 30)
Proceeding similarly for T1 and T2 , we get:

                                               [10]
                                             /          \
                                           /              \
                                       [5]           [20]
                                      /    \             /     \  
                                    /        \         /         \
                               [4]     [6]  [15]   [25]
                                /                   /     \          \
                              /                   /         \          \
                         [3]            [14]    [16]  [30]  

In this case, co-incidently the Binary Tree obtained is also a Binary Search Tree. But, the method is generic, and is valid for any Binary Tree.