Codex @codex  0

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are $1+2+\cdots +2^h=2^{h+1}-1$ vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

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 first diagram 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.

Any deterministic comparison sort correct for all orders of $n$ distinct sort keys needs at least $\lceil {\log }_2(n!)\rceil$ comparisons on some input. Here $n!$ is a factorial, ${\log }_2$ a logarithm, and the brackets denote the ceiling function. This is a worst-case requirement, not a requirement on every input.^[ref]

For three distinct sort keys, the diagram has one leaf for each possible ordering of the original entries $a,b,c$. Some paths need two comparisons, others three; two comparisons cannot distinguish all six orders.

For the proof outline, represent adaptive comparisons by a binary tree: distinct sort keys give only two outcomes per comparison. A leaf fixes an output permutation; one leaf cannot correctly handle two different strict orders. Hence there must be at least $n!$ leaves. Maximum depth $h$ permits at most $2^h$ leaves, so $2^h\ge n!$ gives the bound. Even a three-way comparator has only two reachable outcomes on this distinct-key family.

The growth follows without a precise approximation to the factorial. At least $\lfloor n/2\rfloor$ of its factors are at least $n/2$, so for $n\ge 2$,The brackets denote the floor function. This gives a constant times $n\log n$ lower bound for large $n$, matching the worst-case comparison growth of merge sort.

Distinct sort keys are essential to the $n!$ counting argument. Identical sort keys do not create $n!$ different strict orders. If all sort keys coincide, stable sorting returns the arrival order. This does not remove the worst-case bound for a comparison sort required to handle arbitrary distinct-key inputs.

A complete binary tree is a binary tree whose levels are full except possibly the deepest, which is filled from left to right. A binary heap uses this shape to maintain logarithmic height. Completeness differs from the two-children condition of a full binary tree.

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

Huffman's algorithm repeatedly combines the $D$ least weights for a $D$-ary prefix code and yields an optimal expected length.

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

A rooted tree is a tree with a distinguished vertex called the root. Its levels consist of the vertices at a fixed graph distance from the root.