Binary Tree

A binary tree is either empty or a node with a value, a node.left child, and a node.right child. The top node is the root. A node with no children is a leaf. A node with at least one child is an internal node. A link from parent to child is an edge, and every child has exactly one parent except the root, which has none.

The recursive definition is what makes tree problems feel different from array problems. Each child is itself the root of a smaller binary tree, so most algorithms ask the same question of the left subtree and the right subtree, then combine those answers at the current node.

Interview platforms often write trees in level order. For example, [3,9,20,null,null,15,7] means the root is 3, its children are 9 and 20, 9 has no children, and 20 has children 15 and 7. The word null marks a missing child position, not a real node.

This representation is compact, but the actual pointer shape still matters. A traversal does not jump by array index unless the tree is intentionally stored in an array. The node object points to its children, and missing children are represented by null references.

Three shape words show up constantly. A full binary tree is one where every node has either zero children or two children. A complete binary tree has all levels filled except possibly the last, and the last level is filled from left to right. A perfect binary tree has every internal node with two children and every leaf at the same depth.

These terms are not interchangeable. Heaps are usually complete trees because the array layout depends on no gaps before the end. Perfect trees enable clean formulas such as n = 2^(h + 1) - 1 under the convention that leaf height is 0. Full trees restrict branching but do not guarantee compact levels.

The pointer representation stores each node as an object with val, left, and right. It is flexible: sparse trees, changing shapes, and recursive algorithms are natural. Most LeetCode tree problems use this representation, so you receive a TreeNode root and follow child references.

The array representation stores positions by index, usually with children at 2i + 1 and 2i + 2 for zero-based arrays. It works best for complete trees such as heaps because no space is wasted on many missing positions. For arbitrary sparse binary trees, a pointer representation is usually simpler and smaller.

Binary trees appear as expression trees, decision trees, parse trees, binary search trees, heaps, segment trees, and game trees. The same vocabulary carries across all of them: root, child, parent, subtree, leaf, edge, depth, and height.

In interviews, the most important mental move is to see one node plus two independent subtrees. If you can state what the current node needs from its children, the recursion or traversal order usually follows.