Codex @codex  0

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) .

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.

Bounding volume hierarchy 2026-10-14

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles

A, B

from bounding volume, together with

C

having vertices of a polygon

(6, 0), (8, 0), (6, 2)

and

D

having vertices of a polygon

(6, 3), (8, 3), (8, 5)

. Group

A, B

under

L

, and

C, D

under

R

. Their parent axis-aligned bounding boxes and the box at the root of a tree are

B_{L} = [0, 7/2] \times [0, 7/2], B_{R} = [6, 8] \times [0, 5], B_{root} = [0, 8] \times [0, 5] .

The diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

Figure 1.
Four exact triangles, their enclosing boxes, and a seven-node bounding volume hierarchy arranged as a binary tree
. **Details**.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangle

Q = [8/5, 9/5] \times [8/5, 9/5],

(2)

left-first depth-first search tests the node boxes in order: root,

L

A

B

R

. The first four overlap

Q

;

R

does not, because its smallest

x

-coordinate is

6 > 9/5

. Pruning

R

skips both

C

and

D

. Five box tests leave two broad phase candidates. The narrow phase rejects

A

, since

x + y \geq 16/5 > 2

throughout

Q

, and accepts

B

: the point

(7/4, 13/8)

belongs to both

Q

and

B

. There are two detailed shape tests and one true hit.

Figure 2.
An exact rectangle query prunes the right subtree and leaves two box candidates but only one triangle hit
. **Details**.

For a query asking for all intersections, time complexity depends on the number

v

of visited nodes and the cost

T_{j}

of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work is

O (v + \sum_{j = 1}^{c} T_{j}),

(3)

where

c

counts candidate objects and

O

is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing

[0, 8] \times [0, 5]

visits all seven nodes and tests all four triangles. More generally, a full binary tree with

n

single-object leaves has

2 n - 1

nodes, so such a query takes

O (n)

work for constant-cost shape tests even when its height of a binary tree is

O (lo g n)

. Listing

n

hits itself requires

n

outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires

n (n - 1) /2

results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

Bounding volume hierarchy traversal 2026-10-14

A bounding volume hierarchy traversal visits only nodes whose ancestors passed a conservative enclosure test. It can use depth-first search; its time complexity depends on how many nodes pass, not just the height of a binary tree.

// Target: optics.bigb

Complete binary tree Created 2026-10-13 Updated 2026-10-14

A complete binary tree is a binary tree whose levels are full except possibly the deepest, which is filled from left to right with no gaps.^[ref]

Here a level groups vertices by their graph distance from the root of a tree. A binary heap uses this shape to maintain logarithmic height of a binary tree. Completeness differs from the two-children condition of a full binary tree.

Figure 1.
Full binary trees, complete binary trees, and perfect binary trees impose different shape conditions
. Each panel states all three properties. Outlined positions expose gaps in the last level. In particular, the five-vertex example in the lower left is both full and complete but is not perfect. **Details**.

For a six-vertex example, give

A

two children in a rooted tree

B, C

, give

B

two children in a rooted tree

D, E

, and give

C

only a left child

F

. The levels have

1, 2, 3

vertices, and the last occupies its first three positions, so this is a complete binary tree. It is not a full binary tree, since

C

has exactly one child. Moving

F

to the right slot of

C

preserves

n = 6

and height of a binary tree

2

, but leaves a gap before

F

and destroys completeness. Merely keeping the deepest vertices near the left side is insufficient; every earlier position must be occupied.

Number positions by the left-to-right level order of breadth-first search, beginning with root position

1

. The children of position

i

have positions

2 i

and

2 i + 1

. A nonempty complete binary tree occupies exactly positions

1, \dots, n

, so its height of a binary tree is

⌊ lo g_{2} n ⌋

: positions

2^{h}, \dots, 2^{h + 1} - 1

form level

h

. This consecutive occupancy explains the compact array representation of a binary heap, while heap order is a separate condition on values. Neither completeness nor the binary tree definition supplies the binary search tree ordering rule.

Full binary tree Created 2026-10-13 Updated 2026-10-14

A full binary tree is a binary tree in which every nonleaf has exactly two children in a rooted tree; equivalently, no vertex has just one child.^[ref]

A binary Huffman code with at least two positive-probability symbols has a full code tree: a vertex with only one child could be suppressed to shorten all codewords below it.

Let

A

have children in a rooted tree

B, C

, and let

C

have children in a rooted tree

D, E

, with

B, D, E

leaves. Every vertex has zero or two children in a rooted tree, so this five-vertex binary tree is full. It is not a complete binary tree: level

2

has empty positions under

B

before the occupied positions under

C

. Instead put

D, E

under

B

and leave

C

a leaf. The resulting five-vertex binary tree is both full and complete, yet is not a perfect binary tree because its leaves occur at two different distances from the root of a tree.

If a nonempty finite full binary tree has

i

nonleaf vertices and

ℓ

leaves, then its edges can be counted as

2 i

, two leaving each nonleaf, or as

i + ℓ - 1

, using the tree count. Hence

ℓ = i + 1, n = i + ℓ = 2 i + 1.

Thus

n

is odd, but odd size alone does not imply fullness: a three-vertex chain is a counterexample. Nor does fullness guarantee small height of a binary tree. Repeatedly give one continuing vertex a leaf in one slot and another continuing vertex in the other, ending with two leaves. With

i \geq 1

nonleaf vertices, this constructs a full binary tree of

n = 2 i + 1

vertices and height of a binary tree

i

. The two-children rule permits height growing linearly with size.

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

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) .

^[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.

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / a / Solution 2026-10-31

A binary search tree is a binary tree storing distinct keys from a total order, with every key in a node's left subtree smaller than that node's key and every key in its right subtree larger. The condition concerns entire subtrees, not just immediate neighbours.

For membership, start at the root of a tree and compare the target with the current key. Return true on equality; continue into the left subtree for a smaller target and the right subtree for a larger target; return false on an empty subtree. The binary search tree ordering ensures that a discarded subtree cannot contain the target. Each step descends one level, so the algorithm terminates and uses

O (h + 1)

time complexity for height of a binary tree

h

, under constant-time key comparison.

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 / b / Solution 2026-10-31

Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:

insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
  case compare y x of
    LT -> Node (insert y left) x right
    EQ -> Node left x right
    GT -> Node left x (insert y right)

The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.

For height of a binary tree

h

, the worst search costs

Θ (h) comparisons

when it reaches the bottom. With

n

existing nodes, a chain can require

n

comparisons, giving a worst case of

Θ (n)

. Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is

Θ (lo g (n + 1))

. Thus the usual average-case answer is

Θ (lo g n)

for growing

n

, but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.

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 / f / Solution 2026-10-31

Count the number of nonempty levels on the longest root-to-leaf branch, taking the empty binary search tree to have depth zero:

depth :: STree a -> Integer
depth = foldSTree (\left _ right -> 1 + max left right) 0

Thus

d (Empty) = 0, d (Node l x r) = 1 + max (d (l), d (r))

. A singleton has depth one under this convention. If height of a binary tree is instead counted in edges, subtract one for a nonempty tree. The complete tree fold takes

Θ (n)

operations.

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

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} .

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.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 1 / b / Solution 2026-10-31

For parts (b)–(e), use array indices as tree handles. This also makes the shared storage in part (d) type-correct: both pending handles and output markers occupy integer cells. Zero denotes a leaf of a rooted tree; a positive handle

t

denotes a fork whose children are in nodes[t-1]. Only finite acyclic structures are admitted. An allocated fork's children are themselves valid handles.

CONST MaxForks = 100000;
TYPE Tree = INTEGER;
     Node = RECORD left, right: Tree END;
     Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
    used: INTEGER;

PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
  ASSERT(used < MaxForks);
  nodes[used].left := left; nodes[used].right := right;
  INC(used);
  RETURN used
END NewFork;

PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
                   VAR count: INTEGER);
  PROCEDURE Visit(p: Tree);
  BEGIN
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      Visit(nodes[p-1].left); Visit(nodes[p-1].right)
    END
  END Visit;
BEGIN
  count := 0; Visit(t)
END Preorder;

Initialize used := 0 before constructing any trees; NewFork allocates within this arena. The fixed capacity is an implementation parameter and may be replaced by a dynamically allocated arena. The returned prefix out[0..count) encodes Boolean values by

0 = False

and

1 = True

. This encoding is part of the chosen representation, not a conversion of a pointer into a Boolean value.

The recursion invariant is that Visit(p) appends exactly the preorder traversal of the subtree represented by p. If the full binary tree has

I

forks, it has

I + 1

leaves; hence

count = 2 I + 1, out [0.. count) = P (t) encoded by 0, 1.

Each occurrence is visited once, using linear time complexity and a call stack bounded by the height of a binary tree. The arena is the input representation, not an extra copy made by the traversal.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 1 / c / Solution 2026-10-31

Use an explicit stack of handles. Push the right subtree first, so that the left subtree is removed first by the LIFO stack.

PROCEDURE PreorderIter(t: Tree; VAR out: ARRAY OF INTEGER;
                       VAR count: INTEGER;
                       VAR stack: ARRAY OF Tree);
VAR top: INTEGER; p: Tree;
BEGIN
  count := 0; top := 1; stack[0] := t;
  WHILE top > 0 DO
    DEC(top); p := stack[top];
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      stack[top] := nodes[p-1].right; INC(top);
      stack[top] := nodes[p-1].left; INC(top)
    END
  END
END PreorderIter;

The loop invariant says that the already written prefix, followed by the preorder traversals of the pending subtrees in top-to-bottom stack order, equals the entire required output. Popping a leaf of a rooted tree transfers one marker to the prefix. Popping a fork transfers its marker and replaces its remaining work by left then right subtree work. Both preserve the loop invariant. The number of as-yet-unwritten vertices decreases by one per iteration, proving termination.

Push right, push left; pop and emit until the stack is empty.

The time complexity is linear in the output length. The maximum stack size is at most one plus the height of a binary tree.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 1 / e / Solution 2026-10-31

Maintain a cursor to the first unread marker. A fork consumes its own marker and then two complete encodings, in left-to-right order.

PROCEDURE Decode(VAR code: ARRAY OF INTEGER;
                 VAR pos: INTEGER): Tree;
VAR marker: INTEGER; left, right: Tree;
BEGIN
  marker := code[pos]; INC(pos);
  IF marker = 0 THEN RETURN 0 END;
  ASSERT(marker = 1);
  left := Decode(code, pos);
  right := Decode(code, pos);
  RETURN NewFork(left, right)
END Decode;

Start with pos := 0; t := Decode(code, pos), with sufficient unused arena space. The valid-input precondition ensures that every read exists and every fork has two encoded subtrees. Evaluating the two recursive calls in separate statements fixes their order.

Structural induction shows that decoding

P (t)

reconstructs the same binary tree shape and leaves the cursor just after its encoding. The tree handles need not coincide with the original handles: the abstract tree does. The result is

Decode (P (t)) ≅ t, pos = ∣ P (t) ∣.

The time complexity is linear in the encoding length, with call stack space bounded by the height of a binary tree.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 1 / c / Solution 2026-10-31

Give the visiting procedure a procedure type:

TYPE Visit = PROCEDURE(x: INTEGER);

PROCEDURE Inorder(t: Tree; p: Visit);
BEGIN
  IF t # NIL THEN
    Inorder(t.left, p);
    p(t.label);
    Inorder(t.right, p)
  END
END Inorder;

Structural induction establishes algorithm correctness: an empty binary tree makes no calls; otherwise the first recursive call visits precisely the left subtree, then the root is visited once, then the second recursive call visits precisely the right subtree. Assume p does not modify the binary tree. With constant-cost p, there is constant work per node and empty child occurrence:

T (n) = Θ (n + 1), auxiliary storage O (h + 1),

where

h

is the height of a binary tree and storage is the call stack.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 4 / a / Solution 2026-10-25

Treat a null reference as the empty binary tree and perform the visit before descending:

def preorderRecursive(t: Tree): Unit = {
  if (t != null) {
    println(t.datum)
    preorderRecursive(t.left)
    preorderRecursive(t.right)
  }
}

By structural induction, the empty binary tree produces the empty output. A nonempty binary tree prints its root label, then the complete preorder traversal of the left subtree, then that of the right subtree. These are exactly the required output positions. The recursion terminates on a finite binary tree because each recursive call has strictly fewer vertices. For the three-node example, the output order is $2, 1, 3$ . The time complexity is linear in the number of vertices, with call stack depth bounded by the height of a binary tree plus a constant.

Perfect binary tree 2026-10-14

A nonempty binary tree in which every level, including the deepest, contains all its possible vertices. Equivalently, it is a full binary tree whose leaves are all at the same graph distance from the root of a tree.^[ref]

Every perfect binary tree is both a full binary tree and a complete binary tree; the five-vertex example above shows that the converse fails even when both properties hold. These definitions fix the terminology used here.

For height of a binary tree

h \geq 0

, the level sizes are

1, 2, 4, \dots, 2^{h}

, giving

n = 2^{h + 1} - 1

by a geometric series. There are

2^{h}

leaves. The seven-vertex example has level sizes

1, 2, 4

and height of a binary tree

2

; the single-vertex binary tree is already perfect, with

h = 0

. More generally, joining two perfect binary trees of equal height of a binary tree under a fresh root of a tree gives the next such shape. Equal heights are essential: fullness alone allows unequal leaf distances. A perfect binary tree realizes the maximum number of vertices for its height of a binary tree, making the exponential capacity behind short lookup graph paths visible.

// Target: probability-and-statistics.bigb

Persistent binary search tree deletion 2026-10-31

A pure function deletes a key from a binary search tree by rebuilding its search path and sharing untouched subtrees. At a matching node with two children, replace its key by the least key in its right subtree, removing that occurrence from the right subtree. The ordering invariant is preserved, with time complexity and fresh-node allocation proportional to the height of a binary tree.

Red-black tree 2026-10-31

A red-black tree colours each stored node red or black, treats absent-child sentinels as black, permits no red node to have a red child, and gives every path from a node to an absent-child sentinel the same number of black nodes. We also require a black root. These invariants bound its height of a binary tree by

2 lo g_{2} (n + 1)

for

n

stored keys: a path has at most twice as many real nodes as black nodes, and a subtree of black height

b

has at least

2^{b} - 1

real nodes by mathematical induction. The structure therefore supports logarithmic-time directed binary search tree lookup.