6,720 views

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$

### 1 comment

For detailed explanation following link could be refered ->

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

The answer is $D.$

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.

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

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.

### 1 comment

What you have described is In-order, not Post-order. https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/