Construct a binary search tree from the below given elements and perform the given...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Construct a binary search tree from the below given elements and perform the given operations on constructed tree:
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 removes a branch node. Inserting 60 and 85 creates an unbalanced tree with a deep left spine. To balance the tree, nodes 71 (which creates an isolated subtree after 70's deletion) and 85 (which extends right imbalance) must be removed, resulting in a more balanced structure.
Step-by-step Derivation:
Step 1: Construct initial BST from [82, 90, 98, 70, 75, 71, 99]:
82
/
70 90
/ \ \
71 75 98 99
Step 2: Delete 70 (internal node with two children, replace with inorder successor 71):
82
/
71 90
\ \
75 98 99
Step 3: Insert 60 and 85:
82
/
71 90
/ \ \
60 75 85 98 99
Step 4: Analyze balance. The tree has an imbalanced structure with nodes 71 and 75 on left creating depth, and 85 extending the right. Deleting 71 and 85 removes the unbalanced extremities, leaving a more balanced tree around the core structure.