Binary Trees are one of the most important data structures in computer science.

At the most basic level, a binary tree is a special type of tree made up of nodes, where each node can have at most two children, a left child and a right child.

From this simple structure, we can represent a wide variety of real-world systems like file hierarchies, expression parsing in compilers, search trees for fast lookups, and much more.

In this chapter, we'll cover:

A binary tree is a hierarchical data structure that looks a lot like an upside-down family tree.

This structure represents hierarchical relationships that arrays and linked lists cannot represent efficiently.

Consider a binary tree representing a company's org chart:

A few terms come up throughout this chapter:

Several types of binary trees have specialized properties that make them useful for different tasks. The most common types are described below.

1. Full Binary Tree

2. Complete Binary Tree

3. Perfect Binary Tree

4. Binary Search Tree (BST)

5. Balanced Binary Search Tree

The O(log n) guarantee for a BST only holds when the tree stays balanced. A tree is balanced when its height is close to log₂(n) instead of growing toward n.

If keys arrive in sorted order, a plain BST degenerates into a one-sided chain:

This skewed tree has height n - 1, and search, insert, and delete all degrade to O(n). It is effectively a linked list dressed up as a tree.

Self-balancing trees like AVL trees and Red-Black trees detect this kind of imbalance during insertions and deletions and fix it on the fly using local restructuring operations called rotations. A rotation re-parents three nodes so that the imbalance flattens out without breaking the BST property.

A left rotation at node A (right-heavy chain) looks like this:

Before:

After:

The values still satisfy the BST property (left < parent < right), but the tree's height has dropped from 2 to 1. Real implementations combine left and right rotations (sometimes both, in a "double rotation") whenever a balance condition breaks.

The bookkeeping rules differ between AVL and Red-Black trees:

In both cases, search, insert, and delete are guaranteed O(log n) in the worst case.

Binary trees can be represented in code in two main ways: as an array, or as linked nodes.

There are two common approaches: array representation and linked representation.

This is a non-intuitive but clever way. You can store a tree, level by level, in a simple array.

Array representation is space-efficient when the tree is complete (like heaps) or nearly complete, because there's no wasted memory for pointers. But if the tree is sparse, it can waste memory because unused indices remain empty.

This is the most flexible and common way.

Instead of an array, each node is an object that contains:

The entire tree is just a single variable, root, that points to the very first TreeNode

This representation is the most flexible way to represent trees. It works well for both sparse and dense trees because memory is allocated only for existing nodes.

Traversal means visiting each node in the tree in a specific order. This is the foundation for solving almost every tree-related problem.

There are four main traversals. The first three are variants of Depth-First Search (DFS): they go as deep as possible into one subtree before backing up. The fourth, Level Order, is Breadth-First Search (BFS): it visits the tree one level at a time.

The examples below use this tree:

Visit the entire left subtree first, then the root, then the right subtree.

Visit order for the tree above: [1, 2, 3, 4, 5, 6, 7].

For a Binary Search Tree, the inorder traversal visits nodes in sorted order, which makes it the standard way to walk a BST in ascending key order.

Visit the root first, then the left subtree, then the right subtree.

Visit order: [4, 2, 1, 3, 6, 5, 7].

Preorder is useful for copying or serializing a tree, because the root is recorded before its descendants. If you save nodes in preorder, you can rebuild the same tree structure later.

Visit the left subtree first, then the right subtree, then the root last.

Visit order: [1, 3, 2, 5, 7, 6, 4].

Postorder fits problems where the answer at a node depends on the answers at its children. Examples include computing the size or height of a subtree, deleting a tree (children must be freed before their parent), and evaluating expression trees bottom-up.

Visit the tree one level at a time, from top to bottom and left to right within each level.

Visit order: [[4], [2, 6], [1, 3, 5, 7]] grouped by level, or [4, 2, 6, 1, 3, 5, 7] as a flat list.

Level order fits problems that ask for the shortest path from the root to some target node, or that process nodes by their distance from the root.

This traversal is implemented iteratively using a queue instead of recursion.

The DFS traversals are easiest to write recursively because the call stack does the bookkeeping automatically. Each function call is a small frame that remembers where to resume after the children return.

The downside is that the call stack grows as deep as the tree's height. For a skewed tree of size n, that is n stack frames, which can overflow the call stack on very tall trees. The fix is to switch to an iterative traversal that uses an explicit stack on the heap.

Here is an iterative inorder traversal:

The structure is: walk left, push every node, then pop and visit, then turn right and repeat. Iterative preorder and postorder follow similar stack-based patterns. Iterative level order does not need a stack at all because it is naturally iterative.

Every traversal visits each node exactly once, so the time complexity is O(n). The space complexity is O(h) where h is the height of the tree for DFS variants (recursion stack or explicit stack), and O(w) where w is the maximum width of the tree for level order (the queue holds at most one full level at a time).

For a balanced tree, h is O(log n) and w is O(n/2). For a skewed tree, h becomes O(n) and w becomes O(1).