Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer 15, 10, 23, 25, 20, 35, 42, 39, 30

The correct answer is "option 4".

CONCEPT:

A Binary Search Tree (BST) is also known as an ordered tree or sorted binary tree.

It is a binary tree with the following properties:

1. The left sub-tree of a node contains only nodes with key-value lesser than the node’s key value.

2.  The right subtree of a node contains only nodes with a key-value greater than the node’s key value.

There are three types of traversal:

1. In-order traversal: In this traversal, the first left node will traverse, the root node then the right node will get traversed.

2. Pre-order traversal: In this traversal, the first root node will traverse, the left node then the right node will get traversed.

3. Post-order traversal: In this traversal, the First left node will traverse, the right node then the root node will get traversed.

The in-order traversal of the Binary search tree always returns key values in ascending order.

EXPLANATION:

The pre-order traversal of given BST is:

30, 20, 10, 15, 25, 23, 39, 35, 42.

So, the In-order traversal of the BST is:

10, 15, 20, 23, 25, 30, 35, 39, 42.

The Binary Search Tree is:

[ alt="F1 Shraddha Raju 11.05.2021 D2" src="//storage.googleapis.com/tb-img/production/21/05/F1_Shraddha_Raju_11.05.2021_D2.png" style="width: 159px; height: 137px;">

So the post-order traversal of the tree is:

15, 10, 23, 25, 20, 35, 42, 39, 30

Hence, the correct answer is "option 4".

Related Questions

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?
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?
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?
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 _________
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
What should come in place of question mark (?) in the following question? 2.3̅9̅ + 5 + 6.2̅5̅ + 0.0̅8̅ = ?
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
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?