Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following Inorder and Preorder traversal of a tree Inorder – D B E F A G H C Preorder - A B D E F C G H What is the Postorder Traversal of the same tree

Consider the following Inorder and Preorder traversal of a tree Inorder – D B E F A G H C Preorder - A B D E F C G H What is the Postorder Traversal of the same tree Correct Answer D F E B H G C A

Concept:

  • Inorder and Preorder = Unique Binary tree
  • Inorder and Postorder = Unique Binary tree
  • Preorder and Postorder = More than one Binary tree
  • Inorder Traversal:  Left -> Root -> Right
  • Preorder Traversal:  Root -> Left -> Right
  • Post Order Traversal :  Left -> Right -> Root


Algorithm: (For Inorder and Preorder to make Binary tree)

Step 1: Pick a node in the same sequence in the Preorder

Step 2:  Make left and right of picked node from Inorder

Step 3: Repeat Step 1

Step 4: Repeat Step 2, Loop till the last element in pre order

Explanation:

Binary tree after using this algorithm on pre order and in order: 

[ alt="F2 R.S 20.5.20 Pallavi D5" src="//storage.googleapis.com/tb-img/production/20/05/F2_R.S_20.5.20_Pallavi_D5.png" style="width: 206px; height: 181px;">

Final Binary tree

[ alt="F2 R.S 20.5.20 Pallavi D6" src="//storage.googleapis.com/tb-img/production/20/05/F2_R.S_20.5.20_Pallavi_D6.png" style="width: 201px; height: 186px;">

Using Concept left-> right -> root for post order

Post order = D F E B H G C A

Hence option 3 is the correct answer.

Related Questions

Consider the following statements. S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2 : The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct?
The preorder traversal sequence of a binary search tree is 25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90 Which one of the following is the postorder traversal sequence of the same tree?
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?
Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences. S1: N, M, P, O, Q S2: N, P, Q, O, M S3: M, N, O, P, Q
Postorder traversal of a given binary search tree T produces following sequence of keys: 3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is _________
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode {              treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) {              int value=0;              if (tree != NULL) {              if (tree->leftMostChild == NULL)              value = 1;    else               value = DoSomething(tree->leftMostChild);               value = value + DoSomething(tree->rightSibling);     }               return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the 
In postorder traversal of binary tree right subtree is traversed before visiting root.
Find the postorder traversal of the binary tree shown below.
In preorder traversal of a binary tree the second step is ____________