Constructing Binary Search Tree from Traversals

Constructing Binary Search Tree from Traversals

It is not possible to predict a binary search tree uniquely with one traversal. The one traversal gives ambiguous result.

For example:

Consider the inorder traversal as ABC the trees could be as shown in Fig. 4.11.1.

Thus the only inorder traversal gives two different trees. So, to predict the exact tree from the tree traversals we require atleast two traversals, say, inorder and postorder traversals.

Let us see the procedure of predicting a binary tree from given traversals.

Postorder :H I D E B F G C A

Inorder    :H D I B E A F C G

Step 1:

The last node in postorder sequence is the root node. In above example "A" is the root node. Now observe inorder sequence locate the "A". Left sequence of "A" indicates the left subtree and right sequence of "A" indicates the right sub-tree.

i.e. as shown in Fig. 4.11.2.

Step 2:

Now, with these alphabets H, D, I, B, E observe the postorder and sequences.

Postorder H I D E B

Inorder  H D I B E

Here B is parent node, therefore pictorically tree will be,

Step 3:

With the alphabets H, D and I observe both the sequences.

Postorder H I D

Inorder   H D I

D is the parent node, H is leftmost node and I is the right child of D node. So tree will be as shown in Fig. 4.11.4.

Step 4:

Now we will slove for right sub-tree of root "A". With the alphabets F, C, G observe both the sequences.

Postorder F G C

Inorder F C G

'C' is the parent node, F is the left child and G is the right child. So finally the tree will be as shown in Fig. 4.11.6.

Ex. 4.11.1: Construct a binary tree having the following sequence:

i) Preorder Sequence ABCDEFGHI, ii) Inorder Sequence BCAEDGHFI

Sol. :

Step 1: The very first node in preorder sequence is root node. We will locate this root inorder sequence.