GATE 2014 [Set-1]
January 15, 2024Algorithms
January 16, 2024Question 11091 – Algorithms
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
Correct Answer: D
Question 8 Explanation:
Pre-order is given as
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,
Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,
Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
8, 7, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 8, 7, 6, 5
2, 1, 4, 3, 6, 7, 8, 5
2, 1, 4, 3, 7, 8, 6, 5