TIFR CSE 2014 | Part B | Question: 1

Question

Let $T$ be a rooted binary tree whose vertices are labelled with symbols $a, b, c, d, e, f, g, h, i, j, k$. Suppose the in-order (visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit right subtree, visit root) traversals of $T$ produce the following sequences.

in-order:$a, b, c, d, e, f, g, h, i, j, k$

post-order:$a, c, b, e, f, h, j, k, i, g, d$

How many leaves does the tree have?

• A. THREE.
• B. FOUR.
• C. FIVE.
• D. SIX.
• E. Cannot be determined uniquely from the given information.

Answer 1

We can construct binary tree by postorder and inorder traversal

There we get $5$ leaves of the tree  are $a,c,e,h,j$

So, answer (C) $5$

Answer 2

There are 5 leaves as shown in below fig.