QUESTION 36 Construct a binary search tree from the below given elements and perform the...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
QUESTION 36
Construct a binary search tree from the below given elements and perform the given operations on constructed tree.
Given Elements: 82 90 98 70 75 71 99
Operations:
- I) Delete 70
- II) Insert 60 and 85
Which of the nodes given in options had to be deleted from the resultant tree after performing the given operations to make tree as balanced?
Show answer & explanation
After constructing the BST from [82, 90, 98, 70, 75, 71, 99], deleting 70, and inserting 60 and 85, the tree becomes severely unbalanced with a deep right-skewed branch. To restore balance using AVL tree rotations or rebalancing, nodes 71 and 85 must be removed as they create imbalance at critical points in the tree structure.
Step-by-step Derivation:
Step 1: Build initial BST from [82, 90, 98, 70, 75, 71, 99]:
- Insert 82 (root)
- Insert 90 (right of 82)
- Insert 98 (right of 90)
- Insert 70 (left of 82)
- Insert 75 (right of 70)
- Insert 71 (right of 70, left of 75)
- Insert 99 (right of 98)
Initial tree structure:
82
/
70 90
\
75 98
/
71 99
Step 2: Delete 70 (node with two children - replace with inorder successor 71):
82
/
71 90
\
75 98
99
Step 3: Insert 60 (left of 71):
82
/
71 90
/ \
60 75 98
99
Step 4: Insert 85 (right of 82, left of 90):
82
/
71 90
/ \ /
60 75 85 98
99
Step 5: Analyze balance factor - the right subtree (rooted at 90) is heavier. To rebalance, removing 71 eliminates the left subtree complexity, and removing 85 eliminates the problematic insertion that creates the imbalance. These two deletions restore a more balanced tree structure.