Binary Trees
A Binary Tree is a hierarchical structure where every node has at most two children, forming the basis for complex search and routing algorithms.
The Structure and Its Vocabulary
A binary tree is a hierarchical structure in which each node holds a value and references to at most two children, conventionally named left and right. A node with no children is a leaf; the single node with no parent is the root; every other node has exactly one parent.
'At most two' is the whole definition, and the ordering of the two children is part of it: a left child is not interchangeable with a right one, so two trees holding the same values in mirrored positions are different trees. That distinction matters — it is what makes in-order traversal meaningful.
The vocabulary is where exam answers most often go wrong, so it is worth being exact. The depth of a node is the number of edges from the root down to it, making the root's depth 0. The height of a node is the number of edges on the longest path from it down to a leaf, making every leaf's height 0. The height of the tree is the height of its root.
Two conventions exist — some texts count nodes rather than edges, making a single-node tree have height 1 instead of 0. Neither is wrong, but mixing them produces answers off by one, so state which you are using. The edge convention is more common and gives the empty tree height −1.
Two counting facts follow directly and are worth knowing cold. A binary tree of height h holds at most 2^(h+1) − 1 nodes, achieved when every level is completely filled. Conversely, a tree with n nodes has height at least ⌊log₂ n⌋ — it cannot be shorter — and at most n − 1 when every node has a single child.
- Each node has at most two ordered children: left and right
- Depth counts edges down from the root; height counts edges to the deepest leaf
- Height h holds at most 2^(h+1) − 1 nodes
- n nodes need height at least ⌊log₂ n⌋
Full, Complete, Perfect, Balanced
Four terms describe how thoroughly a tree is filled, and they are routinely confused because three of them sound like synonyms. They are not, and questions frequently turn on the distinction.
A full binary tree — also called strict or proper — is one where every node has either zero or two children, never exactly one. It says nothing about levels being filled; a full tree can be deeply lopsided, with one branch descending far past another.
A complete binary tree has every level completely filled except possibly the last, and the last level's nodes packed to the left with no gaps. This is the property that makes heaps work, and it is the reason a heap can live in an array.
A perfect binary tree has every internal node holding two children and all leaves sitting on the same level. It is the strongest of the three: perfect implies both full and complete. A perfect tree of height h has exactly 2^(h+1) − 1 nodes, of which 2^h are leaves — so just over half of all nodes in a perfect tree are leaves, which is why algorithms that touch only leaves are not much cheaper than ones touching everything.
A balanced tree is a different kind of claim: it constrains height rather than fill. The usual definition requires the left and right subtree heights of every node to differ by at most one. This is the property that guarantees O(log n) operations, and it is what AVL and red-black trees maintain through rotations after every insertion and deletion.
| Type | Requirement | Implies |
|---|---|---|
| Full | Every node has 0 or 2 children | Nothing about shape or height |
| Complete | All levels filled but the last; last packed left | Height is ⌊log₂ n⌋ |
| Perfect | All internal nodes have 2 children; all leaves level | Full and complete |
| Balanced | Subtree heights differ by ≤ 1 at every node | Height O(log n) |
- Full — zero or two children, shape unconstrained
- Complete — filled left to right, gaps only at the end of the last level
- Perfect — every leaf on one level; implies full and complete
- Balanced — a height guarantee, not a fill pattern
Why Height Governs Everything
Almost every operation on a tree walks a path from the root toward a leaf, so its cost is proportional to the height, not to the node count. This one fact explains why so much machinery exists purely to keep trees short.
A balanced tree of n nodes has height O(log n), so a root-to-leaf walk touches about 20 nodes for a million entries. The same n nodes arranged as a degenerate tree — every node with only a right child — have height n − 1. The structure is a linked list wearing tree vocabulary, and every operation degrades to O(n).
This is not a hypothetical worst case. Inserting already-sorted data into an unbalanced binary search tree produces exactly that chain, and sorted input is extremely common. The failure is silent: the code is correct, the tests pass on small shuffled data, and performance collapses in production.
Self-balancing structures exist to make the guarantee unconditional. AVL trees keep subtree heights within one of each other and rebalance with rotations; red-black trees enforce a looser colour invariant that bounds the height at 2·log₂(n+1), rebalancing less often in exchange for slightly taller trees. That trade — stricter balance and faster lookups against cheaper insertions — is why standard libraries generally choose red-black.
Space follows the same logic. Recursive traversal consumes a call frame per level, so stack usage is O(h): about 20 frames for a balanced million-node tree, and a million frames — a stack overflow — for a degenerate one.
- Operation cost tracks height, not the number of nodes
- Balanced gives O(log n); degenerate collapses to O(n)
- Sorted input builds the worst-case chain in an unbalanced BST
- Recursion depth is O(h), so degenerate trees overflow the stack
Terms, operations, and practical uses
Tree Properties
- Root NodeThe singular topmost node of a tree, which has no parent.
- Leaf NodeA node located at the bottom of the tree, characterized by having exactly zero children.
- Internal NodeAny node that is not a leaf; it has at least one child.
Metrics
- Node DepthThe number of edges on the path from the root node to a specific node.
- Tree HeightThe maximum depth across all nodes in the tree. An empty tree has height -1, and a single node has height 0.
- SubtreeA node and all of its descendants, which independently forms a valid tree structure.
Structural Types
- Full Binary TreeA binary tree in which every node has either zero or exactly two children.
- Complete Binary TreeA binary tree where every level is fully filled, except possibly the last, which is filled left-to-right.
- Perfect Binary TreeA binary tree where all internal nodes have two children and all leaves are at the exact same depth.
Build a three-node binary tree
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
root = TreeNode(1, TreeNode(2), TreeNode(3))
print('Root:', root.val)#include <iostream>
using namespace std;
struct BinaryTreeNode {
int val;
BinaryTreeNode *left;
BinaryTreeNode *right;
BinaryTreeNode(int x) : val(x), left(nullptr), right(nullptr) {
}
};
BinaryTreeNode* buildExampleTree() {
BinaryTreeNode* root = new BinaryTreeNode(1);
root->left = new BinaryTreeNode(2);
root->right = new BinaryTreeNode(3);
return root;
}
int main() {
BinaryTreeNode* root = buildExampleTree();
cout << "Root: " << root->val << '\n';
}public class Main {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
System.out.println("Root: " + root.val);
}
}Step through it
Running on root = 1, left = 2, right = 3
Read all 11 Steps
- A single node One node with no children is already a valid binary tree of height 0.
- Add two children B and C attach below A. 'Binary' means at most two children — never three.
- Depth vs height B sits at depth 1: one edge from the root. Height is measured the other way, from a node down to its deepest leaf.
- Extend the left D and E attach under B. The tree is now height 2 on the left.
- Every child is a subtree B with D and E is itself a complete binary tree. That self-similarity is why recursion fits trees so naturally.
- Extend the right F and G attach under C. Every level is now completely filled.
- Perfect tree All leaves sit at the same depth and every internal node has exactly two children. This is a perfect binary tree.
- Counting nodes A perfect tree of height h holds 2^(h+1) - 1 nodes: here 2^3 - 1 = 7. Each level doubles the one above it.
- Why height matters Levels grow by doubling, so height is about log2(n). Any algorithm that walks root-to-leaf costs O(height).
- The degenerate case Insert 1,2,3,4 in increasing order into an unbalanced tree and every node has only a right child.
- A tree became a list With one child per node, height equals n-1 and every operation degrades to O(n). This is what AVL and red-black trees exist to prevent.
Representation and Traversal
The usual representation gives each node a value and two child references, with a null marking an absent child. Memory is O(n), scattered, and the tree is navigated by following pointers.
A complete tree admits a much better option: store it in an array with no pointers at all. Put the root at index 0, and the children of index i sit at 2i + 1 and 2i + 2, with the parent at ⌊(i − 1) / 2⌋. The arithmetic replaces the pointers, memory drops to the values alone, and the elements sit contiguously so traversal is cache-friendly. This is exactly how a binary heap is implemented, and it is why heaps are fast in ways their big-O does not reveal. The scheme only works for complete trees — a sparse tree would leave the array full of unused gaps.
Traversal is where the recursive definition pays off, because a binary tree is defined in terms of smaller binary trees. The three depth-first orders differ only in when the current node is visited relative to its subtrees: pre-order visits the node before both, in-order between them, and post-order after both.
Each has a characteristic use. Pre-order copies or serialises a tree, since the parent is emitted before the children that depend on it. Post-order frees or evaluates one, since children must be handled before their parent. In-order is the one specific to binary trees — on a binary search tree it emits the values in sorted order, which is often the fastest way to check that a tree is a valid BST.
Level-order traversal is the odd one out. It visits nodes level by level using a queue rather than recursion, and it is the tool for anything depth-related: the height of a tree, the nodes on a given level, or the shortest path from the root.
- Children of index i live at 2i+1 and 2i+2 — complete trees only
- Array representation drops the pointers and improves locality
- Pre-, in-, and post-order differ only in when the node is visited
- Level-order uses a queue and answers depth questions