edited by
8,600 views
27 votes
27 votes

The pre-order traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the post-order traversal of this tree is

  1. $2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$
  2. $2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$
  3. $7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12$
  4. $7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12$
edited by

5 Answers

Best answer
28 votes
28 votes

Preoder: $\enclose {circle}{12}\quad \enclose {circle}{8} \quad 6\quad 2\quad 7\quad 9\quad 10\quad 16\quad 15\quad 19\quad 17\quad 20$

Inorder of BST must be sorted in increasing order!

Inorder: $\underbrace{\overbrace{2\quad 6 \quad 7}^{\text{left}}\quad \overset{\text{root}}{\enclose {circle}{8}}\quad \overbrace{9\quad 10}^{\text{right}}}_{\text{left}}\quad \overset{\text{root}}{\enclose {circle}{12}}\quad \underbrace{15\quad 16\quad 17\quad 19\quad 20}_{\text{right}}$

So, Postorder: $2 \quad 7 \quad 6 \quad10\quad9\quad8\quad15\quad17\quad20\quad19\quad16\quad12.$

Answer is B.

edited by
6 votes
6 votes
Sorting the given sequence gives Inorder traversal.

Constructing tree gives Option B as the postorder traversal.
0 votes
0 votes
To find a unique BST (pre-order, in-order) or (post-order, in-order) is required. Here in question the pre-order traversal is given & we can find in-order traversal(in-order of BST is in increasing order of keys). So we got that pair. Now we can construct a BST & for that tree, post-order traversal can be found easily.
Answer:

Related questions

33 votes
33 votes
10 answers
2
Arjun asked Feb 14, 2017
16,620 views
Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are:Note: The height of a tree with a single node is $0$.$4$ and $15$ res...