Binary Search Tree: Insertion, Traversals and Deletion, Worked by Hand
A binary search tree (BST) has one rule: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. Every operation is just that rule applied again and again.
Insertion: follow the rule until you find an empty spot
Insert these values in this order: 50, 30, 70, 20, 40, 60, 80.
- 50 becomes the root.
- 30 < 50, so it goes left of 50.
- 70 > 50, so it goes right of 50.
- 20 < 50 → left; 20 < 30 → left of 30.
- 40 < 50 → left; 40 > 30 → right of 30.
- 60 > 50 → right; 60 < 70 → left of 70.
- 80 > 50 → right; 80 > 70 → right of 70.
The tree:
50
/ \
30 70
/ \ / \
20 40 60 80
The order of insertion decides the shape. Insert the same numbers as 20, 30, 40, 50, 60, 70, 80 and you get a tall chain with every node having only a right child, where search degrades from O(log n) to O(n). That is why balanced trees (AVL, red-black) exist.
The three depth-first traversals
All three visit every node. They differ only in when the node itself is visited relative to its two subtrees.
| Traversal | Order | Result for our tree |
|---|---|---|
| Inorder | Left, Node, Right | 20 30 40 50 60 70 80 |
| Preorder | Node, Left, Right | 50 30 20 40 70 60 80 |
| Postorder | Left, Right, Node | 20 40 30 60 80 70 50 |
Two facts worth stating in a viva:
- Inorder traversal of a BST always gives sorted output. That is a direct consequence of the BST rule, and it is how you verify a tree is a valid BST.
- Preorder is how you copy a tree (you must create the parent before its children). Postorder is how you delete one (you must free the children before the parent).
Search
To search for 60: start at 50, 60 > 50 so go right; at 70, 60 < 70 so go left; found. Each step discards one whole subtree, which is why a balanced BST searches in O(log n).
Deletion: three cases
Case 1: the node is a leaf
Delete 20. It has no children, so simply remove it. Node 30 now has only a right child (40).
Case 2: the node has one child
Delete 30 (now that 20 is gone, it has only the right child 40). Replace 30 by its child 40:
50
/ \
40 70
/ \
60 80
Case 3: the node has two children
Delete 70 from the tree above. It has children 60 and 80. You cannot just remove it, so:
- Find its inorder successor: the smallest value in the right subtree. That is 80 (leftmost node of the right subtree).
- Copy 80 into the node being deleted.
- Delete the original 80 node (a leaf, so Case 1).
Result:
50
/ \
40 80
/
60
You could equally use the inorder predecessor (the largest value in the left subtree, here 60). Both keep the BST rule intact, and examiners accept either if you state which one you use.
Complexity
| Operation | Balanced tree | Worst case (chain) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Checklist for exam answers
- Draw the tree after each insertion, or at least the final tree clearly.
- Write all three traversals if asked, and check inorder is sorted.
- For deletion, name the case (leaf, one child, two children) and say whether you used the successor or the predecessor.
Sumantrak™ is an AI mentor built for Indian engineering, diploma, BCA and BSc CS/IT students — Data Structures, Algorithms, and the rest of your syllabus, explained like this. Free to start →