A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Height is the longest path from root to leaf. A balanced tree has height O(log n), enabling efficient operations. Complete trees have all levels full except possibly the last. These properties directly impact algorithm performance.
Now that you understand how binary trees are structured — nodes with left and right children forming a recursive hierarchy — the next question is: what makes one binary tree better than another? The answer lies in three measurable properties that directly determine how fast tree operations run: height, balance, and completeness.
The height of a binary tree is the number of edges on the longest path from the root to any leaf. A single-node tree has height 0. Why does height matter? Because most tree operations — search, insert, delete — work by walking from the root toward a leaf, examining one node per level. The height is therefore the worst-case number of steps. A tree with n nodes can have height as large as n−1 (a degenerate chain where every node has only one child — essentially a linked list) or as small as ⌊log₂ n⌋ (a perfectly packed tree where every level is full). The difference is dramatic: searching a chain of 1,000 nodes takes 999 steps; searching a tree of height 9 takes at most 9 steps.
A tree is balanced when its height is O(log n) — close to the theoretical minimum. The precise definition varies by context: some definitions require that every node's left and right subtrees differ in height by at most 1 (as in AVL trees), while others allow a constant factor of slack. The important insight is that balance is what separates efficient trees from degenerate ones. If you insert sorted data into a plain binary search tree, you get the worst case: a chain. Self-balancing tree variants (AVL, red-black) maintain balance through rotations during insertion and deletion, guaranteeing O(log n) operations regardless of insertion order.
A complete binary tree has a specific shape: every level is fully filled except possibly the last, which is filled from left to right. A full binary tree is even stricter — every node has either zero or two children, no singles. A perfect binary tree has both properties: every level is completely filled. Complete trees are significant because they pack nodes as tightly as possible, minimizing height for a given number of nodes, and they can be stored efficiently in an array without pointers. The heap data structure exploits this: because a complete binary tree of n nodes always has height ⌊log₂ n⌋ and maps cleanly to array indices (node i's children are at 2i+1 and 2i+2), heaps achieve O(log n) insert and delete with minimal overhead. Understanding these properties gives you the vocabulary to evaluate any tree-based data structure: ask about its height guarantee, and you know its performance story.