Tree Search, Insertion/Deletion in Binary Tree

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Tree Search, Insertion, and Deletion in Binary Tree

Three operations, all following the exact same "compare and go left/right" logic.

🔍 BST Operations

SearchCompare target to current node; go left if smaller, right if larger, repeat until found or you hit an empty spot.

InsertionSearch for where the value WOULD be found; insert it there as a new leaf.

DeletionTrickiest case: deleting a node with two children requires replacing it with its in-order successor (the smallest value in its right subtree) or predecessor, to preserve the BST ordering property.

💡 Practice deleting a node with two children specifically — this is the case that trips people up, since it needs the successor/predecessor replacement, unlike the simpler 0-child or 1-child deletion cases.

All three deletion cases, on one tree

Build a tree by inserting 50, 30, 70, 20, 40, 60, 80 in that order:

50 / \ 30 70 / \ / \ 20 40 60 80 In-order traversal: 20 30 40 50 60 70 80 ← sorted, as it must be

Case 1 — delete 20 (a leaf). Nothing depends on it, so simply remove it and set its parent's left pointer to null.

Result in-order: 30 40 50 60 70 80 ✓ still sorted

Case 2 — one child. Take the tree that remains after 20 was deleted, in which 30 now has only the child 40. Deleting 30 replaces it by that child, so 50's left pointer goes straight to 40.

Starting from 30 40 50 60 70 80 (case 1's result), deleting 30 gives in-order: 40 50 60 70 80 ✓ still sorted Note the dependence on the CURRENT tree: in the original tree 30 has two children (20 and 40), so deleting it there would be case 3 instead. Which case applies is a property of the node's children at the moment of deletion, not of the key.

Case 3 — two children. Go back to the original tree and delete 50, the root. It cannot simply be removed without orphaning a subtree, so it is replaced by its in-order successor: the smallest key in its right subtree, found by going right once and then left as far as possible — here 70, then 60.

Copy 60 into the root, then delete the original 60 node (which is a leaf, so case 1 applies): 60 / \ 30 70 / \ \ 20 40 80 Result in-order: 20 30 40 60 70 80 ✓ still sorted

Why the successor specifically? Because it is the next key in sorted order, so every key in the left subtree is still smaller than it and every key in the right subtree is still larger. Any other choice violates the ordering property somewhere in the tree.

💡 The in-order predecessor — the largest key in the LEFT subtree, here 40 — works equally well by the same argument. Either is correct; say which you are using and stay consistent.

How to check your answer

After any insertion or deletion, the in-order traversal of a BST must come out sorted. That is the definition of the ordering property, and it is a complete check.

💡 In an exam, write the in-order traversal after your deletion and confirm it is ascending. If it is not, the replacement node was wrong — and you will have caught it before the marks are lost, in about ten seconds.

Cost

All three operations cost the height of the tree: search descends one level per comparison, insertion is a search followed by attaching a leaf, and deletion is a search plus at most one more descent to find the successor. So O(log n) on a balanced tree and O(n) on a degenerate one — the same dependence on balance that runs through this whole topic.

Syllabus points

BST search
Insertion & deletion in a BST

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.