Binary tree types

A binary tree allows at most two children at each node. The left and right positions are distinct, even when only one child exists. A binary tree does not automatically enforce an ordering of values: that is an additional property of a binary search tree.

Shapes that sound similar

Term	Rule	Example consequence
Full / proper	Each node has either zero or two children	A node with only a left child breaks the rule
Perfect	Every internal node has two children and all leaves have equal depth	A perfect height-2 tree has seven nodes
Complete	All levels except possibly the last are full; last fills from left to right	Efficient array representation
Height-balanced (informal)	No branch is dramatically deeper than its sibling under a specified balance rule	AVL trees impose a local height-difference bound
Skewed	Every non-leaf has only one child	Height can grow to n - 1

A perfect tree is full and complete, but a full tree is not necessarily perfect. Balance requirements differ between AVL, red-black and other structures: simply calling a tree balanced is not enough to deduce its invariants.

How many nodes fit?

A binary tree of height h edges can contain at most 2^(h+1) - 1 nodes. The bound is reached by a perfect tree. Conversely, a tree with n nodes can have height as low as approximately log2(n) or as high as n - 1 if it degenerates into a chain.

Why shape matters

A complete tree can be stored compactly in an array, because the positions of children can be calculated from the parent’s index. A skewed tree wastes many array positions in a positional layout and makes recursive operations potentially deep. Use the array implementation guide to examine these trade-offs.

Try it: Draw a tree with five nodes that is full but not complete, then explain why the missing left-to-right order disqualifies it from being complete.

Reference: W3Schools binary trees.