UGC NET CSE | June 2011 | Part 2 | Question: 22

Question

Given a binary tree whose inorder and preorder traversal are given by

Inorder : EICFBGDJHK

Preorder : BCEIFDGHJK

The post order traversal of the above binary tree is

• A. I E F C G J K H D B
• B. I E F C J G K H D B
• C. I E F C G K J H D B
• D. I E F C G J K D B H

Answer 1

Preorder - BCEIFDGHJK means root node is B. Inorder - EICFBGDJHK

So search for B in Inorder traversal. Everything to the left of B is left subtree and to the right of B is right subtree in inorder traversal. So we understand that EICF forms the left subtree and GDJHK forms the right subtree of B.

Repeating, this for EICF, we find that C is the root and EI (or IE) forms the left subtree and F forms the right subtree of C. Similarly, for GDJHK, D is the root. G is the left subtree and JHK (or JKH) forms the right subtree.

Therefore, we have the tree as drawn below:

Now finding postorder is very easy. The answer is option (A) IEFCGJKHDB

Answer 2

A. I E F C G J K H D B