Back to Study Material Data Structures and Algorithms

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...

Binary Tree

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).