Binary Trees
A binary tree gives each node at most two children, forming the structural basis for search trees, heaps, and expression trees.
At most two children
A binary tree is a hierarchy in which every node has at most two children, conventionally called left and right. One node is the root; nodes with no children are leaves. The height is the longest root-to-leaf path, and it governs the cost of most operations, since algorithms typically walk a single root-to-leaf path.
Shapes and their properties
- Full: every node has zero or two children
- Complete: all levels full except possibly the last, filled left to right
- Perfect: all leaves at the same depth
- Balanced: height stays O(log n) as nodes are added
Height controls cost
A binary tree with n nodes can have height anywhere from about log n, when balanced, up to n-1, when it degenerates into a chain. Because search, insertion, and traversal follow paths whose length is bounded by the height, keeping a tree balanced is the central concern behind AVL and red-black trees.
Array and pointer storage
A binary tree is usually stored with nodes holding left and right pointers, but a complete binary tree packs perfectly into an array using index arithmetic, which is exactly how a binary heap avoids pointers. The pointer form suits sparse or changing trees; the array form suits dense, complete ones.
What they build
Binary trees are the skeleton of binary search trees for ordered data, heaps for priority queues, expression trees for parsing and evaluation, and Huffman trees for compression. The many balanced variants all start from this basic two-child structure and add invariants to bound the height. Traversing them is covered under tree traversals.