Binary Search Trees: Search, Insertion, Deletion & Successors
“In-order monotonic property, three-case deletion mechanics, successor/predecessor finding, and height degeneracies.”
1.The Binary Search Tree Property & Traversal Order
§ 2.1.A Binary Search Tree (BST) organizes keys so that binary search can be performed dynamically:
forall y in text{LeftSubtree}(x): key(y) < key(x)
forall z in text{RightSubtree}(x): key(z) > key(x)
Because of this ordering, an In-Order traversal (Left -> Node -> Right) visits keys in strictly ascending sorted order.
Successor and Predecessor Algorithms:
To find Successor(x) (the smallest key greater than key(x)):
1. If x.right != null: return the minimum key in x.right (follow left pointers until null).
2. If x.right == null: traverse up parent pointers. The successor is the lowest ancestor p of x such that x lies in p's left subtree.
2.The Three Cases of BST Deletion
§ 2.2.Deleting node z from a BST requires maintaining the search tree property:
- Case 1 (z is a leaf): Simply disconnect z from its parent. O(1).
- Case 2 (z has 1 child): Bypass z by linking z.parent directly to z.child. O(1).
- Case 3 (z has 2 children): Find z's inorder successor y (which lies in z's right subtree and has no left child). Copy y.key into z.key, and delete y from the right subtree using Case 1 or Case 2.
All basic operations (search, insert, delete, min, max, successor) take O(h) time, where h is the tree height.
3. Worked Problem: BST Inorder Successor & Node Deletion Sequence
When deleting a node with 2 children, its successor has at most ONE child (a right child), so the successor deletion never recursively triggers Case 3.
Problem: Keys [50, 30, 70, 20, 40, 60, 80, 35, 45] are inserted into an initially empty BST. Find the Inorder Successor of node 30, and trace the tree structure after deleting node 30.
Step 1: Construct BST from insertion order:
- Root: 50
- Left of 50: 30
- Left of 30: 20
- Right of 30: 40
- Left of 40: 35
- Right of 40: 45
- Right of 50: 70
- Left of 70: 60
- Right of 70: 80
Step 2: Find Inorder Successor of 30:
Node 30 has a right subtree rooted at 40.
Successor is the minimum key in the right subtree of 30.
Following left pointers from 40 leads to 35.
Inorder Successor of 30 = 35.
Step 3: Delete node 30 (Case 3: two children 20 and 40):
- Copy successor key 35 into node 30's position.
- Delete original node 35 from right subtree (node 35 is a leaf, so Case 1).
- Node 40's left child becomes null.
Final Subtree at 35: Left child 20, Right child 40 (with right child 45). BST invariant fully preserved.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Visual thinkers who want to see each algorithm step animated clearly.
GATE-targeted coverage with step-by-step GATE PYQ walkthroughs.