= Height of a binary tree
{title2=$h$}
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\geq1$ <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>.
The convention counts <edges>, rather than <vertices> on the longest <graph path>. Its recursive form is
$$
h(\varnothing)=-1,\qquad h(T)=1+\max\{h(L),h(R)\}\quad(T\ne\varnothing).
$$
<Data Structures and Algorithms edited by Peter Ljunglöf and others/9.1 Binary trees>[Data Structures and Algorithms, section 9.1.2, height pseudocode: null returns -1]{ref}
For a leaf, both <subtrees> are empty, giving $1+\max(-1,-1)=0$. For the mixed four-<vertex> example, $h(C)=h(D)=0$, $h(B)=1+\max(-1,0)=1$, and $h(A)=1+\max(1,0)=2$. The four-<vertex> chain has <height of a binary tree> $3$. A convention that counts <vertices> would add one to every nonempty <binary tree> height, so a height formula must specify its convention.
At distance $d$ from the <root of a tree>, there are at most $2^d$ <vertices>: each <vertex> in the preceding level has at most two <children in a rooted tree>. Summing this <geometric series> and using the longest <graph path> gives, for $n\geq1$,
$$
n\leq2^{h+1}-1,\qquad \lceil\log_2(n+1)\rceil-1\leq h\leq n-1.
$$
The upper bound is attained by a chain; a <perfect binary tree> attains the capacity bound. For $n=4$, the minimum possible <height of a binary tree> is $\lceil\log_2 5\rceil-1=2$, as in the mixed example, while the maximum is $3$. The <binary tree> definition permits both extremes. Small <height of a binary tree> bounds the length of a directed lookup in a <binary search tree>; evaluating the <height of a binary tree> by the displayed <structural recursion> still examines all $n$ <vertices>, requiring $O(n)$ <time complexity> under constant-cost child access and arithmetic.
Back to article page
