Codex @codex  0

 Incoming links: Structural recursion

Binary tree Created 2026-10-13 Updated 2026-10-14

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label

4

, its left child label

2

and its right child label

6

. Attach

1, 3

as the left and right children in a rooted tree of

2

, and

5, 7

as those of

6

. This binary tree has seven vertices, six edges, and height of a binary tree

2

: a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children

1, 2, \dots, 7

, whose height of a binary tree is

6

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels

1

and

7

in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair

(L, R)

of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.^[ref]

Figure 1.
Left and right binary tree child slots distinguish shapes even with just one child
. Solid circles are vertices; outlined squares mark empty binary tree child slots. The first two binary trees differ only in the occupied slot at $A$ . The last two have the same four labels but different height of a binary tree. **Details**.

In the four-vertex mixed example,

A

has left child

B

and right child

D

, while

B

has only a right child

C

. Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus

B

contributes

1 + 0 + 1 = 2

, and

A

contributes

1 + 2 + 1 = 4

. The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.

Ignoring values, let

b_{n}

count finite binary tree shapes with

n

vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relation

b_{0} = 1, b_{n} = \sum_{i = 0}^{n - 1} b_{i} b_{n - 1 - i} (n \geq 1) .

(1)

For each left subtree size

i

, choose its shape and the right subtree shape independently. This yields the Catalan numbers:

b_{1} = 1

b_{2} = 2

, and

b_{3} = 2 + 1 + 2 = 5

. The two shapes at

n = 2

are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.

 Read the full article

Height of a binary tree Created 2026-10-13 Updated 2026-10-14

 View more

For a nonempty binary tree, the largest number of edges on a downward graph path from its root of a tree to a leaf. A single vertex has height of a binary tree

0

; a chain of

n \geq 1

vertices has height of a binary tree

n - 1

. A convenient recursion convention assigns an empty binary tree height

- 1

, giving

h = 1 + max (h_{L}, h_{R})

for the left and right subtrees. A binary search tree lookup visits at most

h + 1

vertices.

The convention counts edges, rather than vertices on the longest graph path. Its recursive form is

h (\emptyset) = - 1, h (T) = 1 + max {h (L), h (R)} (T \neq = \emptyset) .

(1)

^[ref]

For a leaf, both subtrees are empty, giving

1 + max (- 1, - 1) = 0

. For the mixed four-vertex example,

h (C) = h (D) = 0

h (B) = 1 + max (- 1, 0) = 1

, and

h (A) = 1 + max (1, 0) = 2

. The four-vertex chain has height of a binary tree

3

. A convention that counts vertices would add one to every nonempty binary tree height, so a height formula must specify its convention.

At distance

d

from the root of a tree, there are at most

2^{d}

vertices: each vertex in the preceding level has at most two children in a rooted tree. Summing this geometric series and using the longest graph path gives, for

n \geq 1

n \leq 2^{h + 1} - 1, ⌈ lo g_{2} (n + 1)⌉ - 1 \leq h \leq n - 1.

(2)

The upper bound is attained by a chain; a perfect binary tree attains the capacity bound. For

n = 4

, the minimum possible height of a binary tree is

⌈ lo g_{2} 5 ⌉ - 1 = 2

, as in the mixed example, while the maximum is

3

. The binary tree definition permits both extremes. Small height of a binary tree bounds the length of a directed lookup in a binary search tree; evaluating the height of a binary tree by the displayed structural recursion still examines all

n

vertices, requiring

O (n)

time complexity under constant-cost child access and arithmetic.

 Read the full article

Leaf-labelled binary tree 2026-10-24

 View more

A binary tree with each data label stored at a leaf of a tree. One useful Haskell datatype has constructors One a for a leaf and Two (Tree a) (Tree a) for an internal node. Every finite inhabitant has at least one leaf, so this datatype cannot encode an empty leaf sequence. Its natural tree fold has a leaf operation a -> b and an internal operation b -> b -> b; replacing the two constructors by those operations defines the structural recursion.

 Read the full article

List fold 2026-10-24

 View more

The structural recursion that replaces an empty list by a chosen value and a cons constructor by a combining function applied to the head and folded tail. A direct list fold is strict in the list spine at its outermost constructor, even when the combining function does not demand the folded tail. Its algebraic recognition rule is the fold factorisation criterion.

 Read the full article

Null child slot count 2026-10-14

 View more

Every nonempty finite binary tree with

n

vertices has exactly

n + 1

empty binary tree child slots. There are

2 n

slots altogether, and precisely

n - 1

occupied slots, one for each edge of its underlying tree. Therefore

2 n - (n - 1) = n + 1.

(1)

This counts missing child references, not vertices or leaves. In the mixed four-vertex example,

A

has no empty binary tree child slots,

B

has one, and

C, D

each have two:

0 + 1 + 2 + 2 = 5

. The four-vertex chain also has five: one at each of its first three vertices and two at the last. For

n = 0

, there are no vertices and hence no child fields; the empty binary tree instead has a single empty root position if it is represented by a root reference.

A second proof uses the recursive decomposition. Count every empty subtree occurrence, including the root position for the empty binary tree: let

e (\emptyset) = 1

. For a nonempty binary tree,

e (T) = e (L) + e (R)

. If the two subtrees have

n_{L}, n_{R}

vertices, structural induction gives

e (T) = (n_{L} + 1) + (n_{R} + 1) = n + 1

. Distinct empty positions may share the same null value; these are occurrences, not separately allocated objects. This count is useful when analysing the base cases reached by a structural recursion that calls both subtrees of every vertex.

 Read the full article

Past exam of the logic and set theory course of the University of Oxford / 2007 / A / 1 / i / Solution 2026-10-31

 View more

A Boolean valuation is an arbitrary function

v

assigning one of the two truth values to each propositional variable. It extends uniquely to all propositional formulas by following the construction of the propositional formula:

v (p) = v (p), v (\neg A) = \neg v (A), v (A \land B) = v (A) \land v (B), v (A \lor B) = v (A) \lor v (B) .

(1)

For logical implication,

v (A \to B)

is false exactly when

v (A)

is true and

v (B)

is false; otherwise it is true. Here the operations on the right are Boolean operations on truth values. Structural recursion gives existence, and structural induction gives uniqueness: once the immediate subformulas have their values, the outer connective fixes the resulting value.

 Read the full article

Past exam of the logic and set theory course of the University of Oxford / 2009 / A / 2 / b / Solution 2026-10-31

 View more

A first-order structure consists of a nonempty domain

A

, an interpretation

c^{A} \in A

of each constant symbol, a total function

f^{A} : A^{n} \to A

for each

n

-ary function symbol, and a relation

R^{A} \subseteq A^{n}

for each

n

-ary predicate symbol. Logical equality is interpreted as actual identity.

An assignment in a first-order structure is a map

s

from the variables into

A

. It extends recursively to terms:

x^{A} [s] = s (x)

c^{A} [s] = c^{A}

, and

f (t_{1}, \dots, t_{n})^{A} [s] = f^{A} (t_{1}^{A} [s], \dots, t_{n}^{A} [s])

. Atomic truth is determined by membership of the resulting tuple in

R^{A}

, or equality of the two term values. Negation reverses the truth value, and an implication is false exactly when its antecedent is true and its consequent false.

For a universal quantifier,

A, s ⊨ \forall x θ ⟺ A, s [x \mapsto a] ⊨ θ for every a \in A .

(1)

These clauses define a valuation on every formula by structural recursion. Only free-variable values affect a formula's truth; consequently a sentence has the same truth value under every assignment. This is a semantic assignment of domain elements, not a programming assignment operation.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / d / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Traverse the whole original list once for each of its elements:

sml
fun scan [] = ()
  | scan (_ :: xs) = scan xs;

fun scanForEach [] whole = ()
  | scanForEach (_ :: rest) whole =
      (scan whole; scanForEach rest whole);

fun quadratic xs = scanForEach xs xs;

The outer structural recursion runs

n

times, and each scan whole visits

n

constructors. In the ordinary source-evaluation cost model, the time complexity is $Θ (n^{2})$ . This example counts executed traversals, without assuming an optimizing compiler that removes deliberately unused computations.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 1 / e / Solution Created 2026-09-24 Updated 2026-10-14

 View more

For a nonnegative integer parameter

n

, make both branches of a structural recursion execute:

sml
fun binaryWalk 0 = ()
  | binaryWalk n = (binaryWalk (n - 1); binaryWalk (n - 1));

The semicolon sequences two calls, so this is not a conditional choosing just one branch. The recursion tree has

2^{n}

leaves and

2^{n + 1} - 1

calls. Its time complexity satisfies

T (n) = 2 T (n - 1) + Θ (1)

, giving $Θ (2^{n})$ . Here

n

is the parameter specified by the question, not its binary encoding length; only

Θ (n)

calls are simultaneously on the stack.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 6 / c / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Apply structural recursion to the original meal, preserving its internal constructors and replacing each leaf:

fun gluttony (Snack _) replacement = replacement
  | gluttony (Lunch (a, b)) replacement =
      Lunch (gluttony a replacement, gluttony b replacement)
  | gluttony (Feast (a, b, c)) replacement =
      Feast (gluttony a replacement, gluttony b replacement,
             gluttony c replacement);

The type is 'a meal -> 'b meal -> 'b meal: original snack labels are discarded, so the replacement can have a different label type. The constructors introduced by the replacement are not recursively processed; only snacks of the original tree are substituted. The immutable replacement can be shared among occurrences without changing the represented value. Every original Snack is replaced, while the original internal meal structure is retained.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / g / Solution 2026-10-31

 View more

Search as for insertion. Removing a node with at most one nonempty child leaves that child in its place. With two children, use the smallest key in the right subtree as the replacement and remove that occurrence from the right subtree:

delete :: Ord a => a -> STree a -> STree a
delete _ Empty = Empty
delete y (Node left x right) =
  case compare y x of
    LT -> Node (delete y left) x right
    GT -> Node left x (delete y right)
    EQ -> join left right
  where
    -- Join two search trees with every left key below every right key.
    join :: STree a -> STree a -> STree a
    join Empty r = r
    join l Empty = l
    join l r = let (smallest, rest) = takeMin r
               in Node l smallest rest

-- Precondition: the input tree is nonempty.
takeMin :: STree a -> (a, STree a)
takeMin Empty = error "takeMin: empty tree"
takeMin (Node Empty x right) = (x, right)
takeMin (Node left x right) =
  let (smallest, rest) = takeMin left
  in (smallest, Node rest x right)

The call to takeMin occurs only after both empty cases have been excluded. Its structural recursion follows left children until it reaches the minimum label and rebuilds the path with that occurrence removed.

For a matching label

x

and successor

s

, all left labels are below

x < s

, while every label remaining on the right is strictly above

s

. Thus replacing

x

s

preserves the binary search tree invariant. Every other branch preserves the invariant by structural induction. The resulting set is exactly

keys (delete y t) = keys (t) ∖ {y} .

(1)

Whether the key is absent or present, untouched subtrees can be shared. The search path followed by the successor path uses

O (h)

time and fresh nodes for original height of a binary tree

h

, so the worst case is

O (n)

without balancing. This is persistent binary search tree deletion: the original value remains available.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 1 / a / Solution 2026-10-31

 View more

The two constructors encode a natural number by its number of successors. Structural recursion replaces the zero constructor by zero and every successor by one addition:

convert :: Natural -> Integer
convert Zero     = 0
convert (Succ n) = 1 + convert n

Structural induction gives

convert (Succ^{n} Zero) = n

. The output uses unbounded integers, so there is no machine-word overflow.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 1 / c / Solution 2026-10-31

 View more

The natural tree fold replaces each data constructor by the supplied operation:

fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
fold one two (One x)   = one x
fold one two (Two l r) = two (fold one two l) (fold one two r)

Its reconstruction identity is fold One Two = id. More generally a function h equals fold one two on finite trees exactly when h (One x) = one x and h (Two l r) = two (h l) (h r). These equations determine the result by structural induction, expressing why this is the natural structural recursion for this datatype.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 1 / g / Solution 2026-10-31

 View more

Include each child itself, followed by its proper subtrees, while excluding the current root:

proper :: Tree a -> [Tree a]
proper (One _)   = []
proper (Two l r) = (l : proper l) ++ (r : proper r)

Again, occurrences matter: a child with the same value as another child is not removed. The definition is a structural recursion, but its right-hand side uses the original children as well as their recursively computed results.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 1 / a / Solution 2026-10-25

 View more

The right fold replaces the two list constructors by its two arguments; the left fold instead updates an accumulator while traversing the list.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c z []     = z
foldr c z (x:xs) = c x (foldr c z xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl s a []     = a
foldl s a (x:xs) = foldl s (s a x) xs

Thus foldr is the natural list fold: it preserves the constructor arrangement while replacing [] by z and (:) by c. In particular, foldr (:) [] = id. More generally, the fold factorisation criterion says that the defining equations characterize the corresponding structural recursion. Association and lazy evaluation are separate: the accumulator in this definition of left fold is not automatically evaluated at each step.^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 2 / e / Solution 2026-10-25

 View more

A tree fold replaces each constructor by its interpretation:

foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
  combine (foldTree combine zero left)
          equal
          (foldTree combine zero right)

fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []

Induction on the finite tree shows equality with fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type

b

is independent of the key type; other choices can compute a size or another summary using the same structural recursion.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 1 / c / Solution 2026-10-25

 View more

Use these structural recursion definitions in Haskell:

tails :: [a] -> [[a]]
tails xs = xs : ptails xs

ptails :: [a] -> [[a]]
ptails [] = []
ptails (_:xs) = tails xs

ntails :: [a] -> [[a]]
ntails [] = []
ntails xs@(_:rest) = xs : ntails rest

The first definition returns a known outer constructor even when xs is undefined, so null (tails undefined) is False, as required. The pattern in ntails must first determine whether the input is empty. Each suffix of a list is shared with the original list; on a finite input of length

n

, constructing the outer lists takes

O (n)

work and additional outer-list space. No suffix is copied or measured repeatedly.

 Read the full article

Recursion (computer science) Created 2026-10-13 Updated 2026-10-18

 View more

Recursion solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For merge sort, an empty or one-entry array is already sorted, and every larger array is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.

A recursive procedure refers to itself, directly or through another procedure. A recursive call starts another invocation, with its own arguments and local variables; the caller can wait for its returned output. A base case supplies an answer without further recursive calls. To establish algorithm termination, also show that every recursive call progresses in a well-founded relation. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.

Recursion is especially expressive when a data structure already decomposes into smaller structures. A binary tree has two child subtrees, so structural recursion can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a recursive procedure and the recursive process it generates helps connect that compact description to its resource use.^[ref]

 Read the full article

Rooted tree Created 2026-09-28 Updated 2026-10-14

 View more

A rooted tree is a tree with a distinguished vertex, its root of a tree

r

. Choosing

r

turns connections into a hierarchy: every other vertex has a unique parent in a rooted tree, the preceding vertex on its graph path from

r

. Conversely, the vertices whose parent in a rooted tree is

v

are the children in a rooted tree of

v

. Choosing the root of a tree changes this description, while the underlying edges remain the same. Arrows towards the root of a tree can encode the relationship, as in MIT's counting notes; the undirected tree itself needs no arrows. ^[ref]

In the seven-vertex tree above, choose

r = 1

. The levels, grouped by graph distance from the root of a tree, are

{1}

{2, 3}

{4, 5, 6}

{7}

. The children in a rooted tree of

2

are

4, 5

, and the parent in a rooted tree of

7

6

. Choosing

r = 7

instead makes the levels

{7}

{6}

{3}

{1}

{2}

{4, 5}

: now

6

has parent in a rooted tree

7

, reversing their relationship. All six edges survive.

This hierarchy supports structural recursion: process the smaller rooted trees below each vertex, then combine their results. A depth-first traversal of a tree explores one branch before returning; breadth-first search processes successive levels. The lowest common ancestor identifies where two routes from the root of a tree last coincide. For

4, 5

it is

2

when

r = 1

. A binary tree imposes an additional restriction on children in a rooted tree; a general rooted tree has no such bound.

 Read the full article

Tree fold Created 2026-10-24 Updated 2026-10-31

 View more

A structural recursion replacing the empty binary tree by a value and a nonempty node by a combining function on its two folded children and root label. The result type may itself be a function type, allowing a fold to construct a membership predicate or a difference list rather than traversing all branches for every subsequent query.

More generally, choose one operation for each data constructor. For a leaf-labelled binary tree represented by One a | Two (Tree a) (Tree a), the tree fold instead has type signature (a -> b) -> (b -> b -> b) -> Tree a -> b: one operation handles the leaf label, and the other combines the two folded children. Replacing the operations by the original data constructors reconstructs the input, as structural induction proves.

 Read the full article