Trees & heaps formulas

Root at level 0. An upper bound for any binary tree, reached exactly when level $i$ is completely filled.

Reached exactly by a perfect binary tree of height $h$ (every level completely filled).

Reached by any tree with exactly one node per level: left-skewed, right-skewed or zig-zag.

The lower bound follows from $n\le 2^{h+1}-1$. A complete binary tree with $n$ nodes, and so every binary heap, has height exactly $\lfloor {\log }_{2}n\rfloor$.

Holds for every non-empty binary tree, whatever the number $n_1$ of one-child nodes. Here $n_0$ = leaves and $n_2$ = nodes with two children. Proof: count edges two ways. With $n=n_0+n_1+n_2$ nodes there are $n-1$ edges, and each edge hangs below exactly one parent, so $n-1=n_1+2n_2$. Subtracting gives $n_0=n_2+1$.

In a full binary tree every node has 0 or 2 children, so $n_1=0$. With $I$ internal nodes it has $L=I+1$ leaves and $n=2I+1$ nodes in all (always odd). More generally, a full $k$-ary tree (every node has 0 or $k$ children) with $I$ internal nodes has $L=(k-1)I+1$ leaves.

The lower bound holds when the tree is complete. The upper bound is a chain, and every operation then costs $\Theta (n)$ in the worst case. Sorted or reverse-sorted input gives a chain, but so do other orders, such as 1, 5, 2, 4, 3. Of the $n!$ insertion orders of $n$ distinct keys, exactly $2^{n-1}$ give height $n-1$. When all insertion orders are equally likely, the expected height is $\Theta (\log n)$.

An AVL tree needs $\text{BF}\in \{-1,0,1\}$ at every node, with the height of an empty subtree taken as $-1$. A node whose BF becomes $+2$ or $-2$ after an update must be rebalanced by rotation.

The sparsest AVL tree of height $h$ is a root whose two subtrees are sparsest AVL trees of heights $h-1$ and $h-2$. This gives $N(0),N(1),\cdots =1,2,4,7,12,20,33,\dots$ and in closed form $N(h)=F_{h+3}-1$, where $F_1=F_2=1$ are the Fibonacci numbers. Consequently an AVL tree with $n$ nodes has height $h<1.4405{\log }_2(n+2)-0.3277$, which is $O(\log n)$. The maximum number of nodes of height $h$ is $2^{h+1}-1$, as for any binary tree.

In the 1-indexed layout the leaves are at indices $\lfloor n/2\rfloor +1$ to $n$; in the 0-indexed layout at $\lfloor n/2\rfloor$ to $n-1$. In a max-heap with distinct keys the minimum is always at a leaf, since an internal node has a smaller child, and it can be at any leaf. Finding it therefore means scanning the $\lceil n/2\rceil$ leaves, which is $\Theta (n)$.

Bottom-up build-heap calls sift-down (heapify) on every internal node, from the last one back to the root. An $n$-element heap has at most $\lceil n/2^{h+1}\rceil$ nodes at height $h$, and sifting one down costs $O(h)$. The total is $O\left(n{\sum }_{h\ge 0}h/2^h\right)=O(n)$, because ${\sum }_{h\ge 0}h/2^h=2$. It is linear, NOT $\Theta (n\log n)$. Building by $n$ successive inserts instead costs $O(n\log n)$ in the worst case.

Build a max-heap in $\Theta (n)$. Then $n-1$ times: swap the root with the last element of the heap, shrink the heap by 1 and sift down the new root, each costing $O(\log n)$. It sorts in place and is not stable. $O(1)$ auxiliary space assumes an iterative sift-down; the recursive maxHeapify below uses $O(\log n)$ stack space.

The recurrence chooses the root's left subtree size $i$; the right subtree then has $n-1-i$ nodes. The first values are $C_0,\dots ,C_6=1,1,2,5,14,42,132$. $C_n$ is the number of binary tree shapes with $n$ nodes and the number of BSTs on $n$ distinct keys. It also counts the ways to fully parenthesise a product of $n+1$ factors, and the balanced bracket strings of length $2n$. If $n$ distinct labels may be placed freely in the nodes (no BST rule), the number of labelled binary trees is $n!C_n$.