Tree Operations

The previous lesson built the structure of a binary search tree — what it is, the vocabulary that describes its shape, and the ordering property that turns a tree into a searchable index. This lesson supplies the algorithms that operate on that structure: how to traverse a tree in all four standard orders, and how to search, insert into and delete from a BST while preserving its ordering property. Unusually for this course, tree operations are owned here rather than in the algorithms course, because they are inseparable from the structure they walk over; we will, however, cross-reference the recursion lesson in the algorithms course for the recursive mechanism every one of these operations relies on. By the end you should be able to trace any of these operations by hand, write them in OCR-style pseudocode, and explain why an in-order traversal flattens a BST into sorted output.

---

Spec Mapping

This lesson addresses the H446 1.4.2 Data Structures content on operating over trees:

• Traverse a binary tree using the three depth-first orders — in-order, pre-order and post-order — and recognise the breadth-first order; state what each produces and what it is used for.
• Use an in-order traversal of a BST to obtain its data in sorted order (flattening the tree).
• Search a BST for a value, and insert a new value, applying the ordering property at each step.
• Delete a value from a BST across the three cases — a leaf, a node with one child, and a node with two children (resolved with the in-order successor or predecessor).
• Relate the cost of all of these to the tree's height, giving $O(\log n)$O(logn) on a balanced tree and $O(n)$O(n) on a degenerate one.

(Phrasing here paraphrases the specification content; it is not a verbatim quote.)

---

The Recursive Engine Behind Every Tree Operation

Every algorithm in this lesson exploits the single most important fact about a binary tree: it is recursively defined. A binary tree is either empty (a null pointer) or a root node with a left subtree and a right subtree, each of which is itself a binary tree. Because the structure is recursive, the cleanest algorithms over it are recursive too — each one does a little work at the current node and then delegates the rest of the work to its subtrees by calling itself. The base case is always the empty tree (the null pointer), and the recursive case is "do something with this node, then recurse left and/or right". The detailed theory of recursion — base case, recursive case, and the call stack that holds the pending calls — is developed in the recursion lesson of the algorithms course; here we simply use it. It is worth holding one picture in mind throughout: every recursive tree call below is silently pushing a stack frame, so the call stack from the stacks lesson is the hidden structure powering all of these operations.

The standard binary-tree node, carried over from the binary-trees lesson, is a record with a value and two child pointers:

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None       # left subtree (or None)
        self.right = None      # right subtree (or None)

We will use the BST below — built by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order — as the running example for traversals and search:

flowchart TB
    N8((8)) --> N3((3))
    N8 --> N10((10))
    N3 --> N1((1))
    N3 --> N6((6))
    N10 --> N14((14))
    N6 --> N4((4))
    N6 --> N7((7))
    N14 --> N13((13))

---

Tree Traversals

A traversal is a systematic visit of every node in the tree exactly once. The three depth-first traversals — in-order, pre-order and post-order — differ only in when the root is visited relative to its subtrees; the breadth-first (level-order) traversal is a different beast that uses a queue. The names tell you the position of the root: pre-order visits the root before the subtrees, in-order between them, post-order after them. In all three, the left subtree is always processed before the right.

Traversal	Visit order	Output on the example BST	Typical use
In-order	left, root, right	1, 3, 4, 6, 7, 8, 10, 13, 14	listing a BST in sorted order
Pre-order	root, left, right	8, 3, 1, 6, 4, 7, 10, 14, 13	copying / serialising a tree
Post-order	left, right, root	1, 4, 7, 6, 3, 13, 14, 10, 8	deleting a tree; evaluating expression trees
Breadth-first	level by level, left→right	8, 3, 10, 1, 6, 14, 4, 7, 13	level processing, shortest-hop search

In-order traversal

In-order visits the left subtree, then the node, then the right subtree, recursively:

procedure inOrder(node)
    if node == null then
        return                        // base case: empty subtree
    endif
    inOrder(node.left)                 // 1. visit everything smaller
    output node.data                   // 2. visit this node
    inOrder(node.right)                // 3. visit everything larger
endprocedure

def in_order(node, out):
    if node is None:
        return
    in_order(node.left, out)
    out.append(node.data)
    in_order(node.right, out)

Traced worked example

Tracing inOrder(8) on the example BST, the calls nest left-first. The clearest way to see the result is to track when each node's value is actually output (step 2, after its left subtree is exhausted):

Order output	Node	Why now
1st	1	1 has no left child, so it outputs immediately (leftmost node)
2nd	3	after 3's left subtree (just 1) is done
3rd	4	leftmost in 3's right subtree (under 6)
4th	6	after 6's left subtree (4) is done
5th	7	6's right child
6th	8	the root, after its entire left subtree is done
7th	10	after 8's right subtree begins; 10 has no left child
8th	13	leftmost in 10's right subtree (under 14)
9th	14	after 13

The output 1, 3, 4, 6, 7, 8, 10, 13, 14 is the data in ascending sorted order. This is no coincidence: the BST property guarantees everything in a node's left subtree is smaller and everything in its right subtree is larger, and in-order visits smaller, then node, then larger at every level. This is the single most examined fact about traversals.

Pre-order and post-order

Pre-order and post-order are identical except for where the output line sits:

procedure preOrder(node)
    if node == null then return endif
    output node.data                   // root FIRST
    preOrder(node.left)
    preOrder(node.right)
endprocedure

procedure postOrder(node)
    if node == null then return endif
    postOrder(node.left)
    postOrder(node.right)
    output node.data                   // root LAST
endprocedure

Pre-order produces 8, 3, 1, 6, 4, 7, 10, 14, 13 — the root of every subtree appears before its contents, which is exactly what you need to reconstruct the tree later, so pre-order is used to copy or serialise a tree. Post-order produces 1, 4, 7, 6, 3, 13, 14, 10, 8 — every node appears after both its children, which is exactly the order in which you must free/delete nodes (a parent must not be deleted while its children still point to it) and the order in which an expression tree must be evaluated (compute both operands before applying the operator).

Flattening a BST to sorted output

The in-order traversal gives us a free sorting mechanism: build a BST from a list, then read it back in-order. The combination is sometimes called a tree sort.

def tree_sort(values):
    root = None
    for v in values:                   # build the BST
        root = insert(root, v)
    out = []
    in_order(root, out)                # flatten in sorted order
    return out

# tree_sort([8, 3, 10, 1, 6]) -> [1, 3, 6, 8, 10]

This costs $O(n \log n)$O(nlogn) on average (each of $n$n insertions is $O(\log n)$O(logn) on a balanced tree, and the traversal is $O(n)$O(n)), but degrades to $O(n^2)$O(n2) if the input is already sorted and the tree degenerates. The take-away is structural: a BST is a sorted collection in disguise, and in-order is the key that unlocks the sorted view.

Breadth-first traversal (level-order)

Breadth-first visits the tree one level at a time, left to right, and is the odd one out because it is iterative, not recursive, and is driven by a queue rather than the call stack:

procedure breadthFirst(root)
    if root == null then return endif
    queue.enqueue(root)
    while queue is not empty do
        node = queue.dequeue()
        output node.data
        if node.left  != null then queue.enqueue(node.left)  endif
        if node.right != null then queue.enqueue(node.right) endif
    endwhile
endprocedure

On the example tree this outputs 8, 3, 10, 1, 6, 14, 4, 7, 13 — exactly the order the nodes were inserted in this case, but in general just "top-down, left-to-right". The contrast is worth committing to memory: depth-first traversals ride the call stack; breadth-first rides a queue. Swapping the auxiliary structure swaps the order.

Traversals in action — expression trees

The clearest reason the three depth-first orders matter — and a favourite synoptic exam context — is the expression tree. An arithmetic expression can be stored as a binary tree in which every leaf is an operand (a number) and every internal node is an operator, with the operator's two operands as its subtrees. The expression (5 + 3) * 2 becomes:

flowchart TB
    MUL(("×")) --> ADD(("+"))
    MUL --> TWO((2))
    ADD --> FIVE((5))
    ADD --> THREE((3))

What makes this elegant is that the same tree yields all three standard notations of the expression depending on the traversal order chosen:

Traversal	Output	Notation
In-order	5 + 3 × 2	infix (brackets reinstated where precedence needs them)
Pre-order	× + 5 3 2	prefix (Polish notation)
Post-order	5 3 + × 2 (reading 5, 3, +, then 2, ×)	postfix (Reverse Polish)

Post-order is the one that matters most here: it visits both operands of an operator before the operator itself, which is exactly the order in which the expression must be evaluated — you cannot apply + until you have both 5 and 3. That postfix output is precisely the input consumed by the stack-based expression evaluator from the stacks lesson, so an expression tree and a stack together form a complete pipeline from human-readable maths to a computed answer. This single example threads traversals, stacks, trees and compiler design together, which is why examiners reach for it.

Exam Tip: To produce an in-order traversal under exam pressure, draw a loop hugging the outside of the tree from the bottom-left, and read off each node's value as the loop passes underneath it. The values come out in sorted order automatically. Pre-order reads each node as the loop passes its left side; post-order as it passes its right side.

---

Searching a BST

To search for a value, start at the root and let the ordering property steer you: if the target is smaller go left, if larger go right, discarding an entire subtree with each comparison.

function search(node, value)
    if node == null then
        return false                   // base case: ran off the tree
    endif
    if value == node.data then
        return true                    // found it
    elseif value < node.data then
        return search(node.left, value)
    else
        return search(node.right, value)
    endif
endfunction

def search(node, value):
    if node is None:
        return False
    if value == node.data:
        return True
    elif value < node.data:
        return search(node.left, value)
    else:
        return search(node.right, value)

Traced worked example — searching for 7

Step	Current node	Comparison	Action
1	8	$7 < 8$7<8	go left, discarding 8's whole right subtree
2	3	$7 > 3$7>3	go right, discarding 3's left subtree (1)
3	6	$7 > 6$7>6	go right
4	7	$7 = 7$7=7	found

Three comparisons located 7 in a nine-node tree; a linear scan could have needed nine. Each comparison eliminated roughly half the remaining nodes, which is exactly the behaviour of binary search on a sorted array (cross-referenced in the searching-algorithms lesson of the algorithms course). A failed search behaves identically until it reaches a null pointer, at which point the value is known to be absent.

The number of comparisons a search needs is exactly the depth of the target node plus one (the comparison at the node itself). Searching for 7 above took three comparisons because 7 sits at depth 2; searching for the root 8 would take a single comparison; searching for the deepest leaf 13 (depth 3) would take four. This makes the link to tree shape concrete: in a balanced tree no node is deeper than $\approx \log_2 n$≈log2​n, so no search exceeds $\approx \log_2 n$≈log2​n comparisons, whereas in a degenerate tree the deepest node sits at depth $n-1$n−1 and a search for it touches every node. The structural lever — height — is the same one that governs insertion and deletion, because all three follow a single root-to-node path.

---

Inserting into a BST

Insertion reuses the search path, but instead of stopping when it finds the value it continues until it falls off the tree at a null pointer, and inserts the new value there as a new leaf. Crucially, insertion never restructures the existing tree — it only adds a leaf.

function insert(node, value)
    if node == null then
        return new TreeNode(value)     // base case: found the empty slot
    endif
    if value < node.data then
        node.left = insert(node.left, value)
    elseif value > node.data then
        node.right = insert(node.right, value)
    endif
    return node                        // value already present: no change
endfunction

def insert(node, value):
    if node is None:
        return TreeNode(value)
    if value < node.data:
        node.left = insert(node.left, value)
    elif value > node.data:
        node.right = insert(node.right, value)
    return node

Traced worked example — inserting 5