Bissoy.com
Doctors Medicines MCQs Q&A

The pre-order traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the post order traversal of the tree?

The pre-order traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the post order traversal of the tree? Correct Answer 11, 12, 10, 16, 19, 18, 20, 15

Concept:

A binary tree can be traversed in three ways:

  1. Preorder = (Root, Left subtree, Right Subtree)
  2. Inorder = (Left subtree, Root, Right Subtree)
  3. Postorder = (Left Subtree, Right subtree, Root)

 

Explanation:

In case of Binary Search Trees (BST), inorder traversal always sorts the tree nodes into ascending order.

Inorder traversal is 10, 11, 12, 15, 16, 18, 19, 20

Pre-order traversal is 15, 10, 12, 11, 20, 18, 16, 19.

In preorder traversal, the first node would be tree root and values less than root would be part of left

subtree and values greater than root node would form right subtree. So the resultant BST is:

Required Binary Search Tree:

[ alt="F1 R.S Madhu 14.04.20 D1" src="//storage.googleapis.com/tb-img/production/20/04/F1_R.S_Madhu_14.04.20_D1.png" style="width: 111px; height: 195px;">

Post order traversal: 11, 12, 10, 16, 19, 18, 20, 15

Related Questions

We create a binary search tree B1 by inserting the numbers 1, 2, 3, 4, 5 into an empty binary search tree. We create another binary search tree B2 by inserting the numbers into an empty binary search tree in the reverse order. What is the difference between the right-most element of B1 and the left-most element of B2?
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
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. 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 _________
The notification for six different posts - Clerk, PRO, Lecturer, Accountant, Watchman and Principal- are to be released on consecutive Fridays. The schedule of the releasing is to be in accordance with the following conditions: (i) Clerk post must be released a week before the Watchman post. (ii) Lecturer post must not be released immediately after the first release. (iii) PRO post must be released on the Friday following the Friday on which the Principal post is released. (iv) Accountant post must be released on the fifth Friday and should not be immediately preceded by the PRO post. (v) The Watchman post must not be released last. Which of the following notifications will be released immediately after the PRO post?
Which of the following is/are correct about a strictly binary tree? A. A binary tree is called strictly binary tree if every non-­leaf node of it has non empty left and right sub tree B. In strictly binary tree can have two children or no child C. A strictly binary tree with n leaves always contact 2n­-1 nodes
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?
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?
The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________