= Binary tree
{wiki}
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. <Open Data Structures: An Introduction by Pat Morin/6 Binary Trees>[Pat Morin, Open Data Structures, chapter 6: roots, left and right children]{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,\ldots,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>.<Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and others/4.4 Symbol Tables>[Introduction to Programming in Java, section 4.4, Binary search trees: recursive definition and node representation]{ref}
\Image[/binary-tree-ordered-child-slots.png]
{title=Left and right <binary tree child slots> distinguish shapes even with just one child}
{description=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>.}
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,\qquad b_n=\sum_{i=0}^{n-1}b_i b_{n-1-i}\quad(n\geq1).
$$
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.
Back to article page
