BST insertion, deletion and height costs

Objectives and exact tree contract

Extend BST search to updates, successor replacement and height-dependent costs. This lesson uses an ordinary unbalanced binary search tree with distinct keys. Duplicate insertion is rejected without changing the tree; it is not silently routed left or right. At every node all keys in the left subtree are smaller and all in the right subtree are larger. The comparison is a total order. Nodes contain just a key and child links; when used as records, any associated payload must move consistently with a copied key.

Height h is the number of edges on a longest root-to-leaf path; an empty tree has h=−1 and a leaf has h=0. No balancing rotations are performed. Return/update the subtree root after every structural change so that operations on the overall root are handled by the same logic as operations below it. Allocation failure leaves an insertion's existing tree unchanged.

1. Insert by following the search path

Start at root. Compare the proposed key with the current key. Equality stops with “duplicate rejected”; smaller follows left, larger follows right. The first absent child is where a new leaf is attached. For an empty tree the new leaf becomes root. A recursive insert returns the new subtree root; the caller assigns root=insert(root,key), or parent.child=insert(parent.child,key). Ignoring the returned root breaks empty-tree insertion and some deletions.

Worked insertion sequence: 40,20,60,10,30,50,70,25. Root is 40; its children are 20 and 60. Node 20 has children 10 and 30; 30 has left child 25. Node 60 has children 50 and 70. Height is 3 through 40→20→30→25. Inserting 30 again finds equality at the existing 30, so node count remains 8 and no shape changes. Inserting 55 follows 40→60→50 and attaches as 50.right, giving count 9 without increasing height.

Insertion is not “append in sorted order”: input order determines shape. For keys 1,2,3,4,5 inserted in that order, every node has only a right child and height is 4. The inorder traversal is sorted for both this chain and a much shorter BST containing the same keys.

2. Deletion with zero or one child

First search for the key. If absent, return the unchanged subtree. A leaf is replaced by an absent link and released. A node with one child is replaced by that child: the parent link, or overall root, now points to the child. Preserve the replacement link before releasing the removed node. This connects the entire child subtree, not merely its key.

For root 8 with only left child subtree rooted at 3 (which may itself contain descendants), deleting 8 makes 3 the root and preserves all of 3's descendants. For a singleton root 8, deleting 8 makes the tree empty. These are why deletion must communicate the replacement subtree root. A stored parent pointer is optional; recursive return values or a pointer to the incoming child/root link can perform the update.

3. Two children: successor key, then successor node

For a node with two children, choose its inorder successor, the minimum key in its right subtree. Find it by starting at right child and repeatedly following left links. The successor has no left child, although it may have a right child. Copy its key (and associated record payload, when applicable) into the target node, then remove the successor from the right subtree using the zero/one-child cases. Only one physical node is released and total node count falls by one.

Why this preserves order: every original left-subtree key is below the old target key and hence below the successor. The successor is the smallest key in the old right subtree; after its unique occurrence is removed there, every remaining right key exceeds it. With distinct keys and exactly one successor removal, strict inequalities are restored. Copying a successor but leaving its old occurrence creates a duplicate and violates this contract. Choosing the immediate right child instead of the right-subtree minimum is generally wrong.

Worked root deletion on a fresh tree built from 40,20,60,10,30,50,70,45,55: successor of 40 is 45, found along 60→50→45. Replace the root key by 45; delete the old leaf 45 from 50.left. Root remains the same physical object with a new key. Its left subtree is 20 with 10,30; its right is 60 with 50,70, and 50 has right child 55. Inorder is 10,20,30,45,50,55,60,70. There are eight nodes rather than nine.

Successor-with-child example: tree root 20, left child 10, right child 40, and 40.left=30 with 30.right=35. Delete 20: copy 30 to root; replacing the old successor 30 with its right child makes 40.left=35. Dropping 35 would lose a valid subtree. If the successor is the immediate right child, its right child is similarly reattached directly as the target's right child after copying.

4. Identity, cost and shape bounds

Copy-key deletion changes the logical key stored in the target's physical node. External pointers to that node remain pointers to a live object but now observe a different key; pointers to the removed successor become invalid. A transplant-based implementation has a different identity contract. Do not mix their pointer conclusions even when their final key sets agree.

Search, insert and delete take O(h+1) worst-case time for a tree of current height h; finding the successor stays within a root-to-leaf-scale path, so it does not make deletion O(nh). Iterative variants need O(1) auxiliary space when no explicit path stack is retained; recursive versions use O(h+1) call-stack space. Allocation/deallocation costs are separate. An n-node BST may have height n−1, giving O(n) worst-case operations. The smallest possible height is ceil(log2(n+1))−1 for n≥1. O(log n) follows from a height guarantee, not from the word BST alone.

Pitfalls and final check

Declare duplicate and height policies first. Trace the incoming link on every removal, including root. Find the actual successor minimum, reconnect its possible right child, and release exactly one node. Check node count and sorted inorder, but also inspect structure and identities: sorted inorder alone cannot prove that intended nodes remained reachable or that pointer ownership is safe.

Original practice: six single-correct MCQs

These original teaching questions are not previous-year questions. Choose one answer.

P01. Under this lesson’s reject-duplicates policy, inserting 30 into a BST already containing 30:

A. Adds a left duplicate B. Adds a right duplicate C. Replaces the entire tree D. Leaves the tree unchanged

Answer: D

A: This is a different duplicate policy.

B: This is also a different policy.

C: Duplicate detection is not tree replacement.

D: Equality terminates insertion without adding a node.

P02. Insert 1,2,3,4,5 into an initially empty ordinary BST. Edge-height?

A. 2 B. 4 C. 5 D. 0

Answer: B

A: That height is attainable with a better shape, not this insertion order.

B: The five nodes form a chain with four edges.

C: Five counts nodes on the path, not edges.

D: Only a single-node tree has height zero.

P03. A two-child target’s inorder successor is:

A. Maximum of right subtree B. Root of left subtree C. Minimum of right subtree D. Always its immediate right child

Answer: C

A: That could leave smaller keys in the right subtree after replacement.

B: This is not the next larger key.

C: It is the smallest key greater than the target.

D: The right child may have a smaller left descendant.

P04. Root 20 has left 10, right 40; 40.left=30 and 30.right=35. After successor-copy deletion of 20, 40.left is:

A. 35 B. NULL C. 20 D. 10

Answer: A

A: The removed successor’s right child replaces it.

B: This would lose node 35.

C: 20 is the deleted key.

D: 10 remains in the root’s left subtree.

P05. Worst-case operation time for an ordinary n-node unbalanced BST is:

A. Always O(log n) B. O(n) C. O(n²) for every deletion D. O(1) for every search

Answer: B

A: There is no balance guarantee.

B: A height n−1 chain gives linear search/update paths.

C: One path plus successor handling does not require quadratic work.

D: Searching may traverse the whole chain.

P06. In copy-key deletion of a two-child node, which physical node is normally released?

A. Both target and successor B. The target’s left child C. No node D. The original successor node

Answer: D

A: Only one key/node is removed.

B: That is unrelated to the deletion replacement.

C: Leaving all nodes would duplicate the successor key.

D: Target survives with the copied key; the successor occurrence is unlinked.

Sources and scope

GATE CS 2026 bounded extension of existing foundations. Not a whole-subject completion claim. Examples and questions are original.

• Official GATE 2026 CS syllabus, Section 4