= Binary search tree
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. https://opendatastructures.org/newhtml/ods/latex2/binarytrees.html[Pat Morin, Open Data Structures, section 6.2: the binary search tree property]{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>. https://opendatastructures.org/newhtml/ods/latex2/binarytrees.html[Pat Morin, Open Data Structures, section 6.2.1: exact-match searching]{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\to6\to5$, 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\to2\to3\to4\to5$, 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>.
\Image[/binary-search-tree-search-path.png]
{title=Lookup of key $5$ in two <binary search trees> containing the same seven keys}
{description=Orange highlights visited keys and <edges>; green marks the match. The balanced shape has <height of a binary tree> $2$ and requires three visits, while the chain has <height of a binary tree> $6$ and requires five visits for this target.}
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\geq1$. With $n$ entries, $h\leq 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\geq2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BST.java[Sedgewick and Wayne, Algorithms: BST implementation, complexity contract and get method]{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.
\Image[/binary-search-tree-ordering-constraint.png]
{title=The <binary search tree> ordering rule constrains an entire <subtree>}
{description=The valid example has $2<3<4$. The invalid example passes immediate parent-child comparisons, but key $5$ lies in the left <subtree> of key $4$ and violates its inherited upper bound.}
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. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BST.java[Sedgewick and Wayne, Algorithms: BST keys method and inherited-bound isBST check]{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
Back to article page
