edited by
9,174 views
27 votes
27 votes

A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is $5, 3, 1, 2, 4, 6, 8, 7.$ If the tree is traversed in post-order, the sequence obtained would be

  1. $8, 7, 6, 5, 4, 3, 2, 1$
  2. $1, 2, 3, 4, 8, 7, 6, 5$
  3. $2, 1, 4, 3, 6, 7, 8, 5$
  4. $2, 1, 4, 3, 7, 8, 6, 5$
edited by

4 Answers

11 votes
11 votes

Inorder of binary search tree is sorted input sequence 

so inorder= 1, 2, 3, 4, 5, 6, 7, 8.

preorder= 5, 3, 1, 2, 4, 6, 8, 7.

take 1st value from preorder and find its position in inorder sequence .

by doing this u get binary search tree.

after that find post order of tree.

i.e. left child --> right child --> root node.

6 votes
6 votes

Preorder Traversal= 5, 3, 1, 2, 4, 6, 8, 7

In BST Inorder Traversal is sorted input sequence 

so Inorder Traversal= 1, 2, 3, 4, 5, 6, 7, 8.

Using these two traversals we can find the preorder traversal of the tree i.e., 2, 1, 4, 3, 7, 8, 6, 5

1 votes
1 votes
Algorithm Preorder(tree)
   1. Visit the root.
   2. Traverse the left subtree, i.e., call Preorder(left-subtree)
   3. Traverse the right subtree, i.e., call Preorder(right-subtree) 

 

Algorithm Postorder(tree)
   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   3. Visit the root.

Answer:

Related questions

53 votes
53 votes
7 answers
1
Ishrat Jahan asked Nov 3, 2014
13,278 views
The numbers $1, 2, .\dots n$ are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains $p$ nodes. The first number...
64 votes
64 votes
7 answers
3
Ishrat Jahan asked Nov 3, 2014
22,459 views
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h 0$, then the m...
67 votes
67 votes
2 answers
4