Codex @codex  0

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\ge 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

A pointer is a value designating a location in a program's memory model, or a special value such as a null pointer that designates no object. A node in a pointer-linked binary tree stores pointers to its two children. Representation, size, alignment and the validity of dereferencing depend on the programming language and target; 32-bit AAPCS32 data pointers occupy four bytes.

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.

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]

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$ is $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.

A rose tree is an ordered rooted tree in which each vertex can have any finite number of children in a rooted tree. A labelled Haskell representation is data RTree a = Node a [RTree a]. Its tree fold has type (a -> [b] -> b) -> RTree a -> b: recursively fold the children, then combine their results with the current label. Unlike a binary tree, a rose tree has no fixed pair of child positions.

A binary tree organizing a fixed sequence into recursively subdivided contiguous intervals. Each node stores an aggregate for its interval. Range queries and point updates visit logarithmically many nodes; range-update variants store additional information such as a coverage count to maintain the length of a union of active intervals.

A binary tree enumerating every positive reduced fraction exactly once. Begin with boundary fractions $0/1$ and $1/0$; between neighboring fractions $a/b<c/d$, insert their mediant $(a+c)/(b+d)$ and recurse into the two new intervals. The determinant relation $bc-ad=1$ is preserved, and the new denominator is $b+d$.

For a vertex $u$ in a rooted tree, its subtree contains $u$ and every vertex reachable by repeatedly following children in a rooted tree, together with the connecting edges; its root of a tree is $u$. In a binary tree, the left subtree is rooted at the left child, and is empty when that child is absent; the right subtree is defined similarly. A binary search tree constrains every key in these subtrees.

An ultrametric space is a metric space whose metric satisfies the ultrametric inequality. The rational numbers with $d_p(x,y)=|x-y{|}_p$, and their P-adic number completion, are examples. Their geometry organizes points into nested clusters rather than measuring separation along a number line.

For integers $a,b$ and $k\ge 0$, the definition of the P-adic valuation givesThus a closed ball of radius $p^{-k}$ in the integers is a congruence class modulo $p^k$. In the p-adic integers the same closed ball is $a+p^k{\mathbb{Z}}_p$. More shared low-order digits mean a smaller p-adic absolute value of the difference.

The binary tree first splits the sixteen integers into even and odd congruence classes, then refines modulo $4$, $8$, and $16$. Each node fixes one more low-order digit. The leaves $5$ and $13$ share the class $5$ modulo $8$, then separate modulo $16$, so their distance is exactly $1/8$. The leaves are deliberately ordered by their low-order digits; horizontal spacing and edge lengths are layout choices, not the metric. The singleton leaves describe this finite sample; a congruence class modulo $16$ in all p-adic integers remains infinite.

The ultrametric inequality also explains the unusual behavior of balls. Every point of an open ball can serve as its center: if $d(a,b)<r$, then $d(a,x)<r$ if and only if $d(b,x)<r$. Two open balls that intersect are nested, since a point of their intersection serves as a common center and their radii can be compared. The same nesting rule holds for closed balls and for a pair consisting of one open ball and one closed ball.

Every open ball is a clopen set. For a point $y$ outside $B(a,r)$, the open ball $B(y,d(a,y))$ stays outside $B(a,r)$: if $d(y,z)<d(a,y)$, the ultrametric inequality forces $d(a,z)=d(a,y)\ge r$. Hence the complement is an open set. Also every closed ball of positive radius is an open set, because $B(b,r)$ lies in the closed ball of radius $r$ around $a$ whenever $d(a,b)\le r$. A radius-zero closed ball is a singleton and need not be an open set. Distinct points can therefore be separated by a clopen set, proving that an ultrametric space is totally disconnected. These ball properties turn distance thresholds into a hierarchy of compatible clusters. ^[ref]

A base case and a decreasing natural number measure work together. Check that every invocation satisfies its precondition, each base case finishes with the correct output, and every other invocation makes finitely many recursive calls with strictly smaller measure. All local work must also terminate. By well-founded induction, the children finish, so their caller finishes; if their answers are correct and the combination rule preserves the postcondition, the caller is correct too. This proves total correctness, not just correctness conditional on return.

Strict decrease without a lower bound is insufficient: subtracting one forever from a negative integer never reaches zero. Even a positive real-valued measure can decrease indefinitely, as $1,1/2,1/4,\dots$ shows. A well-founded relation rules out that descent. In structural recursion, a proper child subtree of a finite binary tree supplies progress without numeric arguments. The proof obligation is the relation between parent and child instances, together with terminating local work and complete base cases.