Before the questions, make sure you can: use the words root, leaf, parent, child, subtree, depth and height precisely; state the BST property for whole subtrees, not just children; write search and insert both iteratively and recursively, and draw the tree after each insert; delete a key in each of the three cases (leaf, one child, two children using the in-order successor) and draw the tree afterwards; produce the pre-order, in-order, post-order and level-order sequences of a drawn tree; explain why every operation costs O(h) and why inserting sorted keys makes h = n − 1; write recursive utilities (size, leaves, height, isBST with bounds); and describe how a stack-based iterator walks a BST in sorted order.
Play the game "I am thinking of a number between 1 and 100". A smart player guesses 50; you answer "higher" or "lower", and half the numbers disappear with one question. A binary search tree (BST) stores data so that every search plays this game: at each node, one comparison tells you to go left (smaller) or right (bigger), and the other half of the tree is ignored. Unlike a sorted array, a BST also lets you insert and delete without shifting anything. The catch: the game is only fast if the tree stays bushy and short, not long and thin.
Tree vocabulary
A tree in computing is a family tree turned upside down: the ancestor (the root) is at the top, and children hang below their parent. In a binary tree, every person has at most two children, a left one and a right one.
A binary tree is either empty or a node holding a key and two binary trees, its left and right subtrees. That recursive definition is why almost every tree method is recursive: handle the empty tree, then combine the answers for the two subtrees.
50 <- root (depth 0)
/ \
30 70 <- depth 1
/ \ / \
20 40 60 80 <- depth 2
/ \ \
35 45 65 <- depth 3 (leaves 35, 45, 65)
| Term | Meaning (tree above) |
|---|---|
| root | the only node without a parent: 50 |
| parent / child | 40 is the parent of 35 and 45; 60 has one child, 65 |
| leaf | a node with no children: 20, 35, 45, 65, 80 |
| internal node | a node with at least one child: 50, 30, 70, 40, 60 |
| subtree of a node | that node plus all its descendants: the subtree rooted at 40 is {40, 35, 45} |
| depth of a node | number of edges from the root: depth(45) = 3 |
| height of a node | number of edges on the longest path down to a leaf: height(30) = 2 |
| height of the tree | height of the root: 3 |
This course counts edges: a single node has height 0, and the empty tree has height −1. (Some books count nodes, giving 1 and 0 — always check the convention in a question.) A binary tree of height h holds at most 2^(h+1) − 1 nodes, so a tree with n nodes has height at least ⌊log₂ n⌋.
Depth is measured from the top (how far is this node from the root?). Height is measured from the bottom (how far can I go down to a leaf?). The root has depth 0 and the largest height; a leaf has height 0.
The BST property
Think of a library where, at every shelf junction, a sign says "smaller call numbers to the left, bigger to the right". The sign is true for everything down that side, not just for the next shelf. That is why you never have to walk back.
A binary search tree is a binary tree in which, for every node x:
- every key in x's left subtree is less than x's key, and
- every key in x's right subtree is greater than x's key.
The rule is about entire subtrees, not just the two children. In the tree below every parent–child pair looks fine, but 12 sits in the left subtree of 10, so this is not a BST:
10
/ \
5 15
/ \
2 12 <- 12 > 10, but it is in 10's left subtree
Why does it matter? Search for 12 in this tree: at 10, 12 > 10, so you go right to 15, then left to null — "not found", although 12 is in the tree.
Duplicates. In this chapter a BST behaves like a set: inserting a key that is already present does nothing. (Alternatives — a counter in each node, or sending equal keys consistently to one side — exist, but a tree must pick one policy and stick to it.) java.util.TreeSet and TreeMap follow the same "no duplicate keys" rule.
We use this node class:
class Node {
int key;
Node left, right;
Node(int key) { this.key = key; }
}
Search and insert
Searching is the "higher or lower" game: compare, go left or right, repeat until you find the key or fall off the tree. Inserting is the same walk; where you fall off the tree is exactly the empty spot where the new key belongs.
At each node, one comparison tells you which single subtree can contain the key — the other half of the tree is discarded, just like binary search on a sorted array.
// iterative search
boolean contains(int key) {
Node cur = root;
while (cur != null) {
if (key == cur.key) return true;
cur = (key < cur.key) ? cur.left : cur.right;
}
return false;
}
// recursive search
static boolean contains(Node n, int key) {
if (n == null) return false;
if (key == n.key) return true;
return key < n.key ? contains(n.left, key) : contains(n.right, key);
}
Two searches in the tree at the top of the page:
search 45: 50 --(45 < 50, go left)--> 30 --(45 > 30, right)--> 40 --(45 > 40, right)--> 45 found
search 55: 50 --(55 > 50, go right)--> 70 --(55 < 70, left)--> 60 --(55 < 60, left)--> null not found
Only 4 of the 10 nodes are visited each time.
Insert follows the same path until it falls off the tree, and hangs a new leaf there. The iterative version must remember the parent, because by the time cur is null you can no longer attach anything to it:
void insert(int key) {
if (root == null) { root = new Node(key); return; }
Node parent = null, cur = root;
while (cur != null) {
if (key == cur.key) return; // duplicate: ignore
parent = cur;
cur = (key < cur.key) ? cur.left : cur.right;
}
if (key < parent.key) parent.left = new Node(key);
else parent.right = new Node(key);
}
The recursive version uses the "return the new subtree root" pattern: the call returns the (possibly new) root of the subtree, and the caller stores it back into its link.
static Node insert(Node n, int key) {
if (n == null) return new Node(key); // the new leaf
if (key < n.key) n.left = insert(n.left, key);
else if (key > n.key) n.right = insert(n.right, key);
return n; // unchanged subtree root
}
// usage: root = insert(root, key);
Building the example tree, one insert at a time. Insert 50, 30, 70, 20, 40, 60, 80, 35, 45, 65 into an empty tree:
| insert | path followed | new leaf becomes |
|---|---|---|
| 50 | tree is empty | the root |
| 30 | 50 → left | left child of 50 |
| 70 | 50 → right | right child of 50 |
| 20 | 50 → left 30 → left | left child of 30 |
| 40 | 50 → left 30 → right | right child of 30 |
| 60 | 50 → right 70 → left | left child of 70 |
| 80 | 50 → right 70 → right | right child of 70 |
| 35 | 50 → left 30 → right 40 → left | left child of 40 |
| 45 | 50 → left 30 → right 40 → right | right child of 40 |
| 65 | 50 → right 70 → left 60 → right | right child of 60 |
after 50 after 30 after 70 after 20 after 40
50 50 50 50 50
/ / \ / \ / \
30 30 70 30 70 30 70
/ / \
20 20 40
after 60 after 80 after 35
50 50 50
/ \ / \ / \
30 70 30 70 30 70
/ \ / / \ / \ / \ / \
20 40 60 20 40 60 80 20 40 60 80
/
35
after 45 after 65 (final)
50 50
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 60 80
/ \ / \ \
35 45 35 45 65
Every new key becomes a leaf; existing nodes never move during an insert.
- Writing
void insert(Node n, int key)and doingn = new Node(key)whennisnull. Java passes the reference by value: the assignment changes only the local parameter, and the new node is lost. Either return the node or keep a parent pointer. - Calling
insert(root, key)without assigning the result toroot— the very first insert into an empty tree is then lost. - Checking the BST property only between a node and its children (see the tree with 12 above).
Minimum and maximum
The smallest key is as far left as you can go; the largest is as far right as you can go. Just keep turning the same way until there is no road.
The smallest key is the leftmost node: follow left links from the root until the next one is null. The largest is the rightmost node. Neither needs to look at any other branch, so both cost O(h).
static int min(Node n) { // n must not be null
while (n.left != null) n = n.left;
return n.key;
}
In the example tree, min goes 50 → 30 → 20 (20 has no left child): the minimum is 20. Max goes 50 → 70 → 80: the maximum is 80. Note that the minimum is not always a leaf: it is the first node without a left child, and it may still have a right child.
Traversals
A traversal is a tour that visits every room of a house exactly once. The three depth-first tours differ only in when you write the room's name in your notebook: when you first enter it (pre-order), after finishing its left side (in-order), or when you finally leave it (post-order). Level-order is different: it visits the house floor by floor.
A traversal visits every node exactly once — O(n). The three depth-first orders differ only in when the node itself is visited relative to its subtrees:
| Traversal | Order | Tree above | Typical use |
|---|---|---|---|
| pre-order | node, left, right | 50 30 20 40 35 45 70 60 65 80 | copy/serialise a tree (re-inserting in pre-order rebuilds the same BST) |
| in-order | left, node, right | 20 30 35 40 45 50 60 65 70 80 | sorted output of a BST |
| post-order | left, right, node | 20 35 45 40 30 65 60 80 70 50 | anything where children must be finished first: height, size, freeing a tree |
| level-order | level by level, left to right | 50 30 70 20 40 60 80 35 45 65 | shortest-path style problems, printing by levels |
static void inOrder(Node n) {
if (n == null) return;
inOrder(n.left);
System.out.print(n.key + " ");
inOrder(n.right);
}
How does in-order produce 20 30 35 40 45 …? Follow the calls on the left part of the tree:
inOrder(50) first the whole left subtree of 50
inOrder(30) first the whole left subtree of 30
inOrder(20) left is null -> print 20 -> right is null
print 30
inOrder(40)
inOrder(35) prints 35
print 40
inOrder(45) prints 45
print 50
inOrder(70) prints 60 65 70 80 in the same way
Level-order is not recursive; it uses a queue (the Queue ADT you implemented in the lists, stacks and queues chapter): take a node from the front, visit it, add its children at the back.
static void levelOrder(Node root) {
Queue<Node> q = new ArrayDeque<>();
if (root != null) q.add(root);
while (!q.isEmpty()) {
Node n = q.remove();
System.out.print(n.key + " ");
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}
The queue after each visit on the example tree (front of the queue on the left):
| visit | queue afterwards |
|---|---|
| 50 | [30, 70] |
| 30 | [70, 20, 40] |
| 70 | [20, 40, 60, 80] |
| 20 | [40, 60, 80] |
| 40 | [60, 80, 35, 45] |
| 60 | [80, 35, 45, 65] |
| 80 | [35, 45, 65] |
| 35 | [45, 65] |
| 45 | [65] |
| 65 | [] |
To print one line per level, read q.size() at the start of each round and remove exactly that many nodes before starting a new line.
To write a traversal of a drawn tree quickly, trace a line around the outside of the tree, starting left of the root. Pre-order lists a node when you pass its left side, in-order when you pass underneath it, post-order when you pass its right side. For a BST, check your in-order answer: it must be sorted.
Level-order (a queue, visits nearby nodes first — like ripples in a pond) is not the same as pre-order (recursion, i.e. a stack, goes deep first). Both start with the root, so the first few keys can look alike: in the example, both begin with 50, 30, but then pre-order continues with 20 while level-order continues with 70.
Delete: three cases
Removing a person from a family tree is easy if they have no children (just cross them out) or one child (the child moves up into their place). If they have two children, you cannot move both up into one place. Instead you find the person who comes right after them in sorted order — the in-order successor — copy that person into the empty place, and remove the successor from their old spot, which is always an easy case.
First search for the node. Then:
- Leaf — simply remove it (the parent's link becomes
null). - One child — splice it out: the parent's link now points to the node's only child. The whole subtree moves up one level, and the BST property still holds because all those keys were already on the correct side of the parent.
- Two children — find the in-order successor s, the smallest key in the right subtree (go right once, then left as far as possible). Copy s's key into the node, then delete s from the right subtree. s has no left child (otherwise that child would be smaller), so deleting it is always case 1 or case 2.
static Node delete(Node n, int key) {
if (n == null) return null; // key not found
if (key < n.key) {
n.left = delete(n.left, key);
} else if (key > n.key) {
n.right = delete(n.right, key);
} else {
if (n.left == null) return n.right; // leaf or right child only
if (n.right == null) return n.left; // left child only
Node s = n.right; // two children:
while (s.left != null) s = s.left; // in-order successor
n.key = s.key; // copy it up
n.right = delete(n.right, s.key); // delete it below
}
return n;
}
// usage: root = delete(root, key);
Each example below starts again from the full example tree at the top of the page.
Case 1 — delete the leaf 20. 30's left link becomes null:
before after
50 50
/ \ / \
30 70 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80
/ \ \ / \ \
35 45 65 35 45 65
Case 2 — delete 60, which has one child (65). 70's left link now points to 65; 65 moves up one level:
before after
50 50
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 65 80
/ \ \ / \
35 45 65 35 45
Case 3 — delete 30, which has two children. Deleting 30 from the tree at the top of the page: 30 has two children; its successor is 35 (right once to 40, then left to 35). 35 replaces 30 and the leaf 35 is removed:
50
/ \
35 70
/ \ / \
20 40 60 80
\ \
45 65
Check: the in-order sequence is now 20 35 40 45 50 60 65 70 80 — still sorted, just without 30.
Case 3 again — delete the root 50. The successor is 60 (right once to 70, then left to 60). Copy 60 into the root. Then delete the old 60 from the right subtree: it has one child (65), so that is case 2 and 65 moves up:
step 1: successor of 50 is 60 step 2: copy 60 up, then delete old 60 (case 2)
50 60
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 65 80
/ \ \ / \
35 45 65 35 45
Deleting a key that is not in the tree (say 99) walks down to null, returns null into an empty link, and changes nothing.
Using the in-order predecessor (largest key in the left subtree) instead is equally correct; it simply gives a different tree. Questions in this course use the successor unless they say otherwise.
- Looking for the successor in the left subtree, or going "right as far as possible". The successor is right once, then left all the way.
- Forgetting
root = delete(root, key): when the root itself is removed (for example a root with one child), the new root is only known from the return value.
Height decides everything: O(h)
The "higher or lower" game needs only about 7 questions for 100 numbers — if every question splits the range in half. If you ask stupid questions ("is it 1? is it 2? …"), you may need 100. A BST built from sorted keys asks exactly those stupid questions: it becomes a long chain, which is just a linked list.
Search, insert, delete, min and max all follow one root-to-leaf path, so they cost O(h), where h is the height.
| Shape | Height | Cost per operation |
|---|---|---|
| balanced (e.g. random insertion order, on average) | about log₂ n | O(log n) |
| degenerate — a "linked list" | n − 1 | O(n) |
Inserting keys in sorted order produces the degenerate case: inserting 1, 2, 3, 4, 5, 6, 7 gives a chain going right with height 6, and searching it is a linear search. The same keys inserted as 4, 2, 6, 1, 3, 5, 7 give a perfect tree of height 2. Self-balancing trees (AVL, red–black — the structure behind TreeMap) restructure themselves after updates to keep h = O(log n); they are the topic of a later chapter.
insert 1,2,3,4,5,6,7 insert 4,2,6,1,3,5,7
1 4
\ / \
2 2 6
\ / \ / \
3 1 3 5 7
\
4 height 2: at most 3 comparisons
\
5
\
6
\
7 height 6: up to 7 comparisons
A BST is only as good as its height. "BST operations are O(log n)" is true only for a balanced tree; the worst case of a plain BST is O(n).
Recursive utilities
To count the people in a family tree, ask the left child "how many are in your family?" and the right child the same, then add 1 for yourself. Each child asks their own children in the same way. An empty branch answers 0. That is all recursion on trees is.
The recursive definition of a tree gives short, reliable methods. The empty tree is always the base case.
static int size(Node n) {
return n == null ? 0 : 1 + size(n.left) + size(n.right);
}
static int countLeaves(Node n) {
if (n == null) return 0;
if (n.left == null && n.right == null) return 1;
return countLeaves(n.left) + countLeaves(n.right);
}
static int height(Node n) {
if (n == null) return -1; // so that a single node gets 0
return 1 + Math.max(height(n.left), height(n.right));
}
On the example tree these return size 10, 5 leaves and height 3. How height computes 3, from the bottom up:
height(null) = -1
leaves 20, 35, 45, 65, 80: 1 + max(-1, -1) = 0
60: 1 + max(height(null) = -1, height(65) = 0) = 1
40: 1 + max(0, 0) = 1
30: 1 + max(height(20) = 0, height(40) = 1) = 2
70: 1 + max(height(60) = 1, height(80) = 0) = 2
50: 1 + max(2, 2) = 3
These are post-order computations: each node combines answers that its subtrees have already computed. Each visits every node once: O(n).
Checking the BST property. Pass down the open interval (lo, hi) that every key in the current subtree must lie in. Going left tightens the upper bound to the current key; going right tightens the lower bound.
static boolean isBST(Node n, long lo, long hi) {
if (n == null) return true;
if (n.key <= lo || n.key >= hi) return false;
return isBST(n.left, lo, n.key) && isBST(n.right, n.key, hi);
}
// call: isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)
Trace on the "not a BST" tree with 12 from earlier:
node 10 must be in (-inf, +inf) ok
node 5 must be in (-inf, 10) ok (went left of 10: upper bound 10)
node 2 must be in (-inf, 5) ok
node 12 must be in (5, 10) FAIL (went right of 5: lower bound 5; still below 10)
result: false
A check that compares each node only with its own children would say "true" here — which is exactly the mistake the bounds prevent.
(An equivalent check: do an in-order traversal and verify that each key is greater than the previous one.)
A BST iterator
The iterator does the in-order tour, but one step at a time, when you ask for it. The stack is its memory of "places I passed on the way down and still have to come back to" — like leaving a trail of notes on the way into a cave.
TreeSet's iterator returns keys in sorted order without first copying them into a list. The idea: keep a stack of the nodes whose left subtrees are being explored. Start by pushing the path from the root down its left spine. next() pops a node, then pushes the left spine of its right subtree — that is where its successor lives.
class BSTIterator implements Iterator<Integer> {
private final Deque<Node> stack = new ArrayDeque<>();
BSTIterator(Node root) { pushLeft(root); }
private void pushLeft(Node n) {
while (n != null) { stack.push(n); n = n.left; }
}
public boolean hasNext() { return !stack.isEmpty(); }
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
Node n = stack.pop();
pushLeft(n.right); // the successor is down there
return n.key;
}
}
Trace on the smaller tree with keys 50, 30, 70, 20, 40, 60, 80 (stack written top first):
| call | pops | then pushes (left spine of its right subtree) | stack afterwards |
|---|---|---|---|
| constructor | 50, 30, 20 | [20, 30, 50] | |
| next() → 20 | 20 | nothing (no right child) | [30, 50] |
| next() → 30 | 30 | 40 | [40, 50] |
| next() → 40 | 40 | nothing | [50] |
| next() → 50 | 50 | 70, 60 | [60, 70] |
| next() → 60 | 60 | nothing | [70] |
| next() → 70 | 70 | 80 | [80] |
| next() → 80 | 80 | nothing | [] — hasNext() is now false |
The stack never holds more than h + 1 nodes, so memory is O(h). A single next() can push up to h nodes, but every node is pushed and popped exactly once over a full iteration, so a complete traversal costs O(n) — amortised O(1) per next().
Key takeaways
- BST property: for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger — whole subtrees, not just children.
- Search, insert and delete follow one path from the root: O(h). Every new key becomes a leaf.
- Recursive insert/delete return the new subtree root: always write
root = insert(root, key)/root = delete(root, key). - Delete: leaf → remove; one child → splice the child up; two children → copy the in-order successor (right once, then left all the way) and delete it from the right subtree.
- In-order traversal of a BST is sorted. Pre-order = node first, post-order = node last, level-order uses a queue.
- Height is everything: about log₂ n when balanced, n − 1 when keys arrive in sorted order (the tree becomes a linked list).
- Height counts edges: a single node has height 0, the empty tree −1.
isBSTmust pass down (lo, hi) bounds; a BST iterator uses a stack of at most h + 1 nodes and gives amortised O(1) pernext().
Ready? Close the notes and practise.
31 questions. Predict the output before you check — that is the skill the exam measures.