edited by
11,862 views
27 votes
27 votes

The preorder traversal sequence of a binary search tree is $30, 20, 10, 15, 25, 23, 39, 35, 42$. Which one of the following is the postorder traversal sequence of the same tree?

  1. $10, 20, 15, 23, 25, 35, 42, 39, 30$
  2. $15, 10, 25, 23, 20, 42, 35, 39, 30$
  3. $15, 20, 10, 23, 25, 42, 35, 39, 30$
  4. $15, 10, 23, 25, 20, 35, 42, 39, 30$
edited by

2 Answers

Best answer
42 votes
42 votes

Since it is a binary search tree, its inorder traversal produces a sorted sequence i.e. $\text{10, 15, 20, 23, 25, 30, 35, 39, 42}$.

Now given inorder and preorder traversals, we get following tree :

From this, we can give postorder traversal sequence as $\text{15, 10, 23, 25, 20, 35, 42, 39, 30}$ i.e., option (D).

edited by
Answer:

Related questions

41 votes
41 votes
4 answers
1
Arjun asked Sep 23, 2014
12,116 views
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?$O(1)$$O(\log n)$...
52 votes
52 votes
9 answers
3