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.

Destructive binary search tree flattening 2026-10-31

Turn a binary search tree into a sorted doubly linked list by reusing each linked list node's left and right child fields as predecessor and successor fields. An inorder traversal determines the required order. A recursive implementation first saves both child references, flattens the disjoint child subtrees, and splices their endpoints around the root. Structural induction proves that it preserves every original entry exactly once and produces reciprocal links with null outside endpoints. An explicit stack implements the same traversal without recursive calls; each original right child must be saved before its field is overwritten. Both versions take linear time complexity and

O (h + 1)

auxiliary space for original height

h

. The old binary search tree representation is consumed, so outside aliases must not continue to interpret the changed links as child pointers.

Inorder traversal 2026-10-13

An inorder traversal of a binary tree uses recursion to visit the left subtree, output the current vertex, and visit the right subtree; an empty subtree outputs nothing. This is a depth-first traversal of a tree with output between the two recursive calls. It produces sorted keys for a binary search tree, but arbitrary labels in a binary tree need not appear in total order.

// Target: computer-science.bigb

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

Use the empty list for an empty subtree, and join the left result, the current label and the right result:

flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []

Thus

flatten (Node l x r) = flatten (l) + + [x] + + flatten (r)

. This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below

x

and every right label above

x

, proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.

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

Use pattern matching on the two data constructors, concatenating the left subtree's inorder traversal, the root label, and the right subtree's inorder traversal:

data Tree = Leaf | Fork Tree Int Tree

inorder :: Tree -> [Int]
inorder Leaf = []
inorder (Fork l x r) = inorder l ++ [x] ++ inorder r

Here Leaf represents the empty binary tree, rather than a labelled leaf. The printed declaration uses type; an executable Haskell algebraic data type requires data, as above. By structural induction, the two equations return precisely the prescribed inorder traversal:

inorder (Fork (l, x, r)) = inorder (l) + + [x] + + inorder (r) .

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

Split the half-open array segment at its midpoint, using one entry for the root:

PROCEDURE MakeTree(VAR u: ARRAY OF INTEGER;
                   a, b: INTEGER): Tree;
VAR m: INTEGER; t: Tree;
BEGIN
  IF a = b THEN RETURN NIL END;
  m := a + (b-a) DIV 2;
  NEW(t);
  t.label := u[m];
  t.left := MakeTree(u, a, m);
  t.right := MakeTree(u, m+1, b);
  RETURN t
END MakeTree;

The precondition is

0 \leq a \leq b \leq LEN (u)

. Set

n = b - a

. For

n > 0

the child sizes are

⌊ n /2 ⌋

and

n - 1 - ⌊ n /2 ⌋

, differing by at most one. The same construction in both subtrees proves subtree-size balance at every node. Structural induction also gives the inorder traversal

u [a .. m)

, followed by

u [m]

, followed by

u [m + 1.. b)

, hence precisely

u [a .. b)

; no sortedness assumption is needed.

Exactly

n

records are allocated. Each nonempty recursive call makes two child calls, so there are

2 n + 1

calls including empty segments. Under constant-cost allocation and reference parameter passing,

T (n) = Θ (n + 1), inorder (t) = u [a .. b), t is nearly balanced .

For positive

n

this is proportional to

b - a

; the empty case takes constant time. The call stack has

O (1 + lo g (n + 1))

depth.

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

Use destructive inorder traversal by right rotations. A right tree rotation preserves inorder traversal but moves the first unvisited node closer to the root:

PROCEDURE InorderDestructive(t: Tree; p: Visit);
VAR q: Tree;
BEGIN
  WHILE t # NIL DO
    WHILE t.left # NIL DO
      q := t.left;
      t.left := q.right;
      q.right := t;
      t := q
    END;
    p(t.label);
    t := t.right
  END
END InorderDestructive;

The outer loop invariant states that the labels already passed to p, followed by the inorder traversal of t, equal the original inorder traversal. The remaining nodes form a binary tree disjoint from the nodes already visited. The inner loop invariant preserves the remaining inorder traversal: if the old root is

y

, its left child is

x

, and the three unchanged subtrees are

A, B, C

, then both shapes have order

A, x, B, y, C

Figure 1.
A right tree rotation preserves inorder traversal and exposes the next node
. **Details**.

At inner-loop exit, t.left = NIL, so the root is the first remaining node. Visiting it and replacing t by t.right preserves the outer loop invariant. The procedure changes child pointers and makes the old root reference unusable as the original binary tree. Assume p neither changes the binary tree nor depends on its old shape.

Every label is visited in inorder using O (1) auxiliary space .

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 5 / d / iii / Solution 2026-10-31

Replace suspended recursive calls by an explicit stack for an inorder traversal. Save each original right child before overwriting that link:

def flattenIterative(): (Tree, Tree) = {
  val pending = new scala.collection.mutable.Stack[Tree]
  var current = root
  var start: Tree = null
  var end: Tree = null
  while (current != null || pending.nonEmpty) {
    while (current != null) {
      pending.push(current)
      current = current.left
    }
    val t = pending.pop()
    val nextSubtree = t.right
    t.left = end
    if (end == null) start = t else end.right = t
    t.right = null
    end = t
    current = nextSubtree
  }
  root = null
  (start, end)
}

The method belongs to the concrete class owning root. Clearing root records that ownership has transferred to the returned doubly linked list; callers retain both returned endpoints. The inner loop invariant says that the current subtree lies before all its pending ancestors in inorder traversal; pushing and descending left preserves this fact. Its loop variant is the number of entries along the remaining left-child path, a finite decreasing quantity.

The outer loop invariant says that start through end is precisely the already emitted sorted prefix, with reciprocal links and null outside endpoints. current and the pending ancestors describe exactly the remaining traversal in order; original links that are still needed have been retained. A pending ancestor has not yet had its right child overwritten. The next popped entry is therefore the next sorted entry. Saving nextSubtree preserves its future work before assigning t.right = null; linking it to end extends the prefix by exactly one entry. The number of original entries not yet emitted is an outer loop variant, since each full outer iteration emits one. At exit nothing remains, proving the same preservation and ordering postconditions as the recursive version.

Each entry is pushed and popped once, giving

O (n + 1)

time complexity and

O (h + 1)

auxiliary space. No new Tree entries are allocated. The historical mutable stack interface provides the push and pop operations used here; its later deprecation does not change their meaning.^[ref]

Preorder traversal Created 2026-10-25 Updated 2026-10-31

Visit a rooted tree's root before recursively visiting its child subtrees in their specified order. For a binary tree, the order is root, left subtree, right subtree. Unlike inorder traversal, this interpretation stores an internal node's label before either child's labels.

Scala 2.12 mutable Stack API documentation 2026-10-31

www.scala-lang.org/api/2.12.6/scala/collection/mutable/Stack.html

Official historical API documentation for the mutable stack: the empty constructor, push, pop and nonEmpty support an explicit inorder traversal stack. The API's deprecation notices concern later collection choices; they do not remove these documented operations from the cited version.

Splaying 2026-10-31

In ordinary bottom-up splaying, locate the selected node by a binary search tree search and repeatedly move it toward the root. If its parent is the root, perform a zig step. Otherwise use a zig-zig step when the node and its parent occupy the same left/right directions, or a zig-zag step when their directions differ. Each tree rotation preserves the inorder traversal and hence the represented key order. The process ends with the selected key at the root. Unsuccessful access policies can instead move the last visited node to the root; arguments about successful calls should say the requested key exists.