in DS edited by
6,720 views
26 votes
26 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$
in DS edited by
6.7k views

1 comment

For detailed explanation following link could be refered ->

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

1
1

4 Answers

32 votes
32 votes
Best answer

The answer is $D.$

edited by
10 votes
10 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.

5 votes
5 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 vote
1 vote
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.

edited by

1 comment

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

0
0
Answer:

Related questions