Consider the given nodes are inserted into an empty binary search tree in the given order:...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider the given nodes are inserted into an empty binary search tree in the given order:
13, 20, 16, 22, 30, 55, 8
What will be the location of the postorder successor of node 20 in the array representation of the binary search tree?
(Note: Array indexing begins from 0)
Show answer & explanation
The postorder traversal of the BST is: 8, 16, 30, 55, 22, 20, 13. The postorder successor of 20 is 13 (the node that comes after 20 in postorder). In level-order array representation [13, 20, 8, 16, 22, 30, 55], node 13 is at index 0. However, in postorder array representation, the elements are arranged as [8, 16, 30, 55, 22, 20, 13], placing 13 at index 6.
Step-by-step Derivation:
Step 1: Build the BST by inserting 13, 20, 16, 22, 30, 55, 8 sequentially.
- Insert 13: becomes root
- Insert 20: goes right of 13
- Insert 16: goes left of 20
- Insert 22: goes right of 20
- Insert 30: goes right of 22
- Insert 55: goes right of 30
- Insert 8: goes left of 13
Tree structure:
13
/
8 20
/
16 22
30
55
Step 2: Perform postorder traversal (Left, Right, Root):
Postorder: 8, 16, 30, 55, 22, 20, 13
Step 3: Identify postorder successor of 20.
In postorder sequence, 20 appears at position 5, so its successor is 13 (at position 6).
Step 4: The postorder successor (node 13) is at array index 6 in postorder array representation.