Motivation
A binary search tree is useful because its shape records comparison decisions.
At a node with key x, one comparison tells us which entire subtree can be
discarded: a smaller target can only be on the left, and a larger target can
only be on the right. Search, insertion, minimum, maximum, successor, and
deletion are therefore not six unrelated procedures. They are consequences of
one ordering invariant.
That perspective also prevents a common complexity error. A BST operation
follows one root-to-leaf path, so its cost is controlled by the tree height
h, not automatically by log n. A well-shaped tree may have logarithmic
height, while a tree formed by an unfortunate insertion order may degenerate
into a chain. Here “balanced” is used only as a shape description for a tree
whose height is O(log n), not as the name of a maintenance algorithm. This
section develops the core algorithms without introducing
AVL trees, red-black trees, rotations, or any other balancing algorithm; those
topics are outside the source-backed scope of this unit.
Definitions
Definition
Binary search tree invariant
In this unit, a binary search tree (BST) is a binary tree whose nodes have
distinct comparable keys. At every node v, every key in v.left is strictly
smaller than v.key, and every key in v.right is strictly larger than
v.key. Each left and right subtree must itself satisfy the same condition.
The words every key matter. Checking only that the immediate left child is
smaller and the immediate right child is larger is insufficient. A deeply
nested key can violate an ancestor's bound even while every parent-child pair
looks locally plausible. Equivalently, recursive validation carries an
allowable interval: the left subtree inherits a new upper bound v.key, and
the right subtree inherits a new lower bound v.key.
The distinct-key convention comes from the course source. An implementation must therefore document what happens when insertion receives an existing key. It may reject the insertion or replace the stored value, as the lecture ADT does, but it must not create a second node with the same key.
Definition
Height convention
The height h is the number of nodes on a longest downward path from the root
to a leaf. Thus an empty tree has height 0, a one-node tree has height 1,
and every nonempty tree has height
1 + max(height(left), height(right)).
Search, minimum, and maximum
Search repeatedly compares the target with the current root. Equality ends the
search; a smaller target selects the left subtree; a larger target selects the
right subtree. Reaching NIL proves absence because every discarded subtree
lies on the wrong side of an earlier comparison.
It helps to state the loop invariant explicitly. At the start of every iteration, if the target exists anywhere in the original tree, then it exists in the subtree rooted at the current node. The comparison and the BST invariant justify replacing that subtree by exactly one child subtree. When the current node becomes empty, the invariant says there is no remaining place in which the target could occur. This is stronger than saying that the procedure “did not happen to find” the key: it explains why the negative answer is complete.
SEARCH(root, key):
v = root
while v != NIL:
if key == v.key: return v
if key PRECEDES v.key: v = v.left
else: v = v.right
return NIL
The minimum follows left pointers until no smaller-key subtree remains. The maximum follows right pointers symmetrically.
MINIMUM(v): MAXIMUM(v):
while v.left != NIL: while v.right != NIL:
v = v.left v = v.right
return v return v
These procedures require a nonempty starting subtree. If an API permits an
empty input, it should return a distinguished result or report that no extremum
exists rather than dereference NIL.
Minimum and maximum do not compare against a target, but they rely on the same ordering information. If a current node has a left child, that child and every candidate below it are smaller than the current key, so the current node cannot yet be the minimum. Once the left child is empty, no smaller key can occur in that subtree. The maximum argument reverses left and right. In particular, the minimum or maximum need not be a leaf: the minimum may still have a right child, and the maximum may still have a left child.
Insertion
Insertion performs an unsuccessful search. It remembers the last nonempty node as the new node's parent, then attaches the new leaf on the side selected by the final comparison.
INSERT(root, key):
if root == NIL: return NEW_NODE(key)
parent = NIL
v = root
while v != NIL:
parent = v
if key == v.key: return root // duplicate rejected here
if key PRECEDES v.key: v = v.left
else: v = v.right
if key PRECEDES parent.key: parent.left = NEW_NODE(key)
else: parent.right = NEW_NODE(key)
return root
The new node is inserted as a leaf. No old key changes position, which makes the invariant-preservation argument particularly direct.
The empty-tree case is important in a recursive implementation because the returned node becomes the root of a new one-node subtree. On every recursive return, the caller must store that possibly changed subtree root back into its left or right field. Ignoring the returned root can silently lose an insertion. The same observation becomes even more important for deletion, where removing the root of a subtree routinely changes which node represents that subtree.
Inorder successor
Definition
Inorder successor
The inorder successor of a node x is the node visited immediately after x
in an inorder traversal. In a distinct-key BST, it is also the node containing
the smallest key strictly greater than x.key. The maximum node has no
successor.
There are exactly two structural cases.
- If
x.rightis nonempty, the successor isMINIMUM(x.right). - Otherwise, move upward while
xis a right child. The first ancestor for which the path comes from its left child is the successor. If no such ancestor exists, returnNIL.
SUCCESSOR(x):
if x.right != NIL: return MINIMUM(x.right)
p = x.parent
while p != NIL and x == p.right:
x = p
p = p.parent
return p
The second case needs parent pointers, as the tutorial observes, or an equivalent saved search path from the root. Merely storing left and right child pointers is not enough to climb to ancestors.
Why do we skip ancestors reached from a right branch? Such an ancestor was already visited before its entire right subtree during inorder traversal, so it cannot come after the current node. The first ancestor reached from a left branch has not yet been visited: inorder must finish the ancestor's left subtree, including the current node, before visiting that ancestor. This also explains the failure case for the maximum key. Its path to the root never finds an unvisited ancestor entered from the left.
Deletion
Deletion first searches for the key, then distinguishes the number of children of the matching node.
- A leaf is replaced by
NIL. - A node with only one child is replaced by that child.
- A node with two children is replaced by its inorder successor, the minimum node of the right subtree. The predecessor, the maximum of the left subtree, is an equally valid symmetric choice.
The following source-aligned recursive version copies the successor record and then removes its old occurrence. In pointer-owning code, “copy record” must respect the program's memory-ownership policy.
DELETE(t, key):
if t == NIL: return NIL
if key PRECEDES t.key:
t.left = DELETE(t.left, key)
else if key > t.key:
t.right = DELETE(t.right, key)
else:
if t.left == NIL: return t.right
if t.right == NIL: return t.left
s = MINIMUM(t.right)
t.record = COPY(s.record)
t.right = DELETE(t.right, s.key)
return t
The successor has no left child: if it did, that left child would be a smaller key in the same right subtree, contradicting minimality. Consequently, the recursive removal of the successor reduces to a zero-or-one-child case.
The first two deletion cases are sometimes presented as three separate cases: leaf, only-left-child, and only-right-child. The pseudocode combines them because returning the right subtree handles both a missing left child with a real right child and a leaf whose right subtree is also empty. The next branch symmetrically returns the left subtree. This compact form does not remove any logical case; it simply lets an empty subtree act like an ordinary return value.
Deletion also separates logical correctness from memory management. The abstract result is a new root for the modified subtree. A concrete C program must additionally release exactly the removed node, avoid using an address after it has been freed, and decide whether copying a record means copying its owned data or only its pointer fields. Those details do not change the key ordering proof, but a correct ordering algorithm can still become an incorrect program if ownership is mishandled.
Theorem/Proposition
Theorem
Search-path exclusion principle
At a BST node v, if the target key k is smaller than v.key, then no node
in v.right can contain k; if k is larger, no node in v.left can contain
k. Therefore search may discard one whole subtree after each comparison.
Theorem
Core updates preserve the BST invariant
Assume the input tree has distinct keys and satisfies the BST invariant. Inserting a new distinct key at the first empty search position preserves the invariant. Deleting a key by the zero-child, one-child, or successor/predecessor two-child rule also preserves the invariant.
Theorem
Height-sensitive operation bound
Search, minimum, maximum, insertion, successor, and deletion each take O(h)
time on a BST of height h, provided node comparison, pointer access, and
record replacement take constant time. Their worst case over all n-node BST
shapes is therefore O(n).
Proof sketch or proof idea
For the search-path principle, suppose k is smaller than v.key. The invariant says every
key in v.right is greater than v.key, hence also greater than k; equality
with k is impossible there. The larger-target case is symmetric. Applying
this reasoning at each visited node proves search correctness: returning a
matching node is sound, and reaching NIL after all valid directions are
exhausted proves the key is absent.
For insertion, all existing subtrees remain unchanged. Let p be the parent
of the new leaf. Every earlier comparison placed the search within the correct
range inherited from all ancestors. The final comparison puts the key left of
p if it is smaller and right of p if it is larger. Thus the new leaf obeys
both its parent bound and every ancestor bound.
For deletion, returning the only child in the zero-or-one-child case removes a
node without changing the relative order of the surviving keys. In the
two-child case, let s be the right-subtree minimum. Every left-subtree key is
smaller than the deleted key and therefore smaller than s. Every remaining
right-subtree key is at least s, and after the old occurrence of s is
removed, every one is strictly greater than the copied key. The replacement
therefore satisfies both sides of the invariant. The predecessor argument is
symmetric.
Finally, each algorithm moves only along a constant number of ancestor or
descendant paths. No such path contains more than h nodes. Two-child deletion
first reaches the target and then descends within its right subtree; the two
path lengths still sum to at most a constant multiple of h, so the result is
O(h) rather than O(h^2).
The height statement can be related carefully to the number of nodes. Any nonempty tree has height at most the number of nodes, because a simple downward path cannot repeat a node. A reasonably even binary-tree shape places many nodes on each level and has height proportional to the logarithm of the node count. At the other extreme, if every node has only one child, the height equals the node count. The BST invariant permits both shapes: it constrains key placement relative to ancestors, not the relative sizes or heights of the two subtrees. Therefore no logarithmic guarantee follows from “BST” alone.
Worked examples
Worked example
Build the tutorial BST and trace a search
Insert the tutorial sequence
11, 6, 8, 19, 1, 13, 17, 42, 16
from left to right. The resulting relationships are:
11
|- left: 6
| |- left: 1
| `- right: 8
`- right: 19
|- left: 13
| `- right: 17
| `- left: 16
`- right: 42
Searching for 16 compares along
11 -> 19 -> 13 -> 17 -> 16: right, left, right, left, found. No node in an
opposite subtree needs inspection. MINIMUM(root) follows 11 -> 6 -> 1, and
MAXIMUM(root) follows 11 -> 19 -> 42.
Notice that the comparison count is determined by depth, not by numerical distance. Although sixteen is close in value to seventeen, reaching it still requires all five nodes on its root path. Conversely, finding eleven ends after one comparison even though the tree contains keys both much smaller and much larger. The structure, rather than arithmetic difference between keys, determines the work.
Worked example
Trace all successor cases
In the same tree, the successor of 13 is 16: node 13 has a right subtree,
and 16 is its leftmost node. Node 8 has no right subtree. Moving upward,
the path first reaches 6 from the right, so we continue; it then reaches 11
from the left, making 11 the successor. Node 42 has neither a right subtree
nor a qualifying ancestor, so its successor is NIL.
Worked example
Delete 19 by both source-backed strategies
The node 19 has two children. With the predecessor strategy, the largest key
in its left subtree is 17. Replace 19 by 17, then remove the old 17;
its only child 16 becomes the right child of 13. The right subtree of 11
is now rooted at 17, with left subtree 13 -> right 16 and right child 42.
With the successor strategy, the smallest key in the right subtree is 42.
Replace 19 by 42, then remove the old leaf 42. The right subtree of 11
is now rooted at 42, whose left subtree remains rooted at 13 with
13 -> right 17 -> left 16. The two results have different shapes but the
same sorted key set, and both satisfy the invariant.
An inorder audit makes the preservation visible. Before deletion the affected subtree has keys thirteen, sixteen, seventeen, nineteen, and forty-two in that order. After either strategy it has thirteen, sixteen, seventeen, and forty-two. Exactly the requested key disappears; all other relative ordering is unchanged. This sorted audit is a useful check, although sorted inorder output alone should not replace the direct subtree-bound proof above.
Worked example
The same keys can give very different heights
Insert 4, 2, 6, 1, 3, 5, 7. The resulting well-shaped BST has n = 7 and
height h = 3, so a root-to-leaf operation visits at most three nodes. Insert
the same keys in order 1, 2, 3, 4, 5, 6, 7; every key becomes a right child,
giving h = 7. The algorithms are unchanged, but their cost changes from
O(log n) for this well-shaped family to O(n) for the degenerate chain.
This comparison describes shapes only; it does not teach a balancing method.
Common mistakes
Common mistake
Checking only immediate children
The condition “left child smaller, right child larger” does not validate a whole BST. Every descendant must respect every ancestor bound. An out-of-range grandchild is enough to invalidate the tree.
Common mistake
Assuming the successor always lies in the right subtree
That rule applies only when the node has a right subtree. Otherwise the answer may be an ancestor, and the maximum node has no successor at all.
Common mistake
Copying a successor but forgetting to remove it
Two-child deletion is not finished after copying the replacement record. The old successor or predecessor occurrence must also be deleted, or uniqueness is violated.
Common mistake
Writing O(log n) without a height assumption
The unconditional bound is O(h). It becomes O(log n) only when the tree
shape has logarithmic height; a degenerate BST has h = n.
Other implementation errors include losing the returned subtree root during a
recursive update, dereferencing NIL when taking an extremum of an empty tree,
and inserting duplicate nodes without defining a consistent duplicate policy.
Summary
- The strict BST invariant orders entire subtrees, not just adjacent nodes.
- Search discards one impossible subtree after every comparison; minimum and maximum follow the left and right spines.
- Insertion attaches a leaf at the first empty search position.
- A successor is either the right-subtree minimum or the first qualifying ancestor reached from a left branch.
- Deletion has zero-child, one-child, and two-child cases; the last uses the successor or predecessor and removes its old occurrence.
- Correctness follows by showing that every update preserves inherited key bounds.
- The core operations are
O(h): logarithmic on a well-shaped tree and linear on a degenerate one. No balancing algorithm is assumed here.
Exercises
Checkpoint
A tree has root 20, left child 10, right child 30, and node 10 has right child 25. Why is it not a BST?
Identify the ancestor bound that the nested node violates.
Checkpoint
In a BST containing 5, 10, 12, 15, 18, and 20, node 15 has right subtree rooted at 20 with left child 18. What is the successor of 15?
Apply the correct structural case before comparing candidates.
Checkpoint
Using the tutorial BST, trace an unsuccessful search for 14 and state where insertion would attach it.
Record every comparison from the root to NIL.
Checkpoint
Why can the right-subtree minimum used in two-child deletion have no left child?
Argue from the meaning of minimum, not from a diagram.
Checkpoint
For n distinct keys inserted in strictly increasing order, determine h and the search cost for the maximum under this unit's height convention.
Describe the resulting shape first.
Solutions
Solution · Solution 1
Node 25 lies in the left subtree of 20, so every ancestor bound requires
25 to be smaller than 20. This is false. The fact that 25 is larger than 10 does not repair the
violation against root 20.
Solution · Solution 2
Because node 15 has a right subtree, use its right-subtree minimum. Starting
at 20 and moving left reaches 18, so the successor is 18, not the right
child 20.
Solution · Solution 3
The comparisons say 14 is larger than 11, smaller than 19, larger than
13, and smaller than 17; the left child of 17 is 16, so 14 is again
smaller and the search reaches its empty left
child. Insertion attaches 14 as the left child of 16. The full trace is
11 -> 19 -> 13 -> 17 -> 16 -> NIL.
Solution · Solution 4
If the minimum node s of the right subtree had a left child, that child's key
would be smaller than s.key while still belonging to the same right subtree.
That contradicts the choice of s as the minimum.
Solution · Solution 5
Increasing insertion makes every new node the right child of the previous
node, so the tree is a chain with h = n. Searching for the maximum visits all
n nodes and therefore takes Theta(n), consistent with the general O(h)
bound.