Binary Tree
A binary tree is a tree in which every node has at most two children, referred to as the left child and the right child. This restriction to two children i...
Defining the Binary Tree
A binary tree is a tree in which every node has at most two children, referred to as the left child and the right child. This restriction to two children is simple, but it unlocks a rich family of algorithms and enables efficient recursive problem decomposition. Binary trees appear as the foundation for binary search trees, heaps, expression trees, and Huffman coding trees.
A full binary tree is one where every node has either zero or two children — no node has exactly one child. A complete binary tree fills levels from left to right, with all levels fully filled except possibly the last, which is filled from the left. A perfect binary tree has all internal nodes with exactly two children and all leaves at the same level. A perfect binary tree of height h contains exactly 2 to the power of h plus one minus one nodes.
Expression trees are a compelling use case: the expression (3 plus 4) times (2 minus 1) can be stored as a binary tree where each internal node is an operator and each leaf is an operand. Evaluating the expression is then a simple post-order traversal.
Height, Balance, and Node Count
The height of a binary tree strongly influences operation performance. A perfectly balanced binary tree of N nodes has height O(log N), meaning operations that walk from root to leaf are fast. An unbalanced tree, in the worst case, degrades to a linked list with height O(N), losing all efficiency advantages.
You can compute the height of a binary tree recursively: height(node) equals one plus the maximum of height(node.left) and height(node.right), with height(null) equal to negative one by convention. The number of nodes in a complete binary tree can be counted in O(log squared N) time by comparing the leftmost and rightmost depths at each level, which is faster than a naive O(N) traversal.
A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most one. Checking balance is done in O(N) with a single post-order pass that returns height and a balanced flag simultaneously.
Worked Example and Common Interview Patterns
Worked example: given a binary tree, determine whether it is symmetric. A tree is symmetric if the left subtree is a mirror of the right subtree. The recursive solution checks: isMirror(left, right) returns true when both are null; false when exactly one is null; and otherwise checks that left.value equals right.value and isMirror(left.left, right.right) and isMirror(left.right, right.left). This runs in O(N) time and O(H) space where H is the height of the tree.
Many interview problems decompose naturally on binary trees by asking "what do I know about the current node, and what do I need from each subtree?" Identifying whether a problem needs pre-order, in-order, or post-order traversal is the key insight. Post-order is appropriate when a parent's answer depends on both children's answers. Pre-order suits top-down problems like printing paths from root to leaf.
Interview tip: always clarify whether the binary tree can be unbalanced before estimating time complexity. Stating O(log N) is only correct for balanced trees; for a general binary tree, the worst case is O(N).