Overview#

A binary tree is a tree structure in which each node has at most two child nodes. It can represent hierarchical relationships and also serves as the foundation for structures such as search trees, heaps, expression trees, and syntax trees.

The most important thing when learning binary trees is to establish two perspectives:

• Recursive perspective: a tree consists of a root node, a left subtree, and a right subtree;
• Traversal perspective: visit each node in some order and maintain the answer during the visit.

Many seemingly different binary tree problems ultimately come back to “what information does the current node need to obtain from its left and right subtrees.”

Prerequisites

• Recursion: binary tree problems are usually broken down into left and right subtrees
• Traversal order: preorder, inorder, and postorder correspond to different processing timings
• Null nodes: boundary conditions are usually defined starting from null

Problem Definition#

A binary tree node contains three parts:

1
value
2
left  -> left subtree
3
right -> right subtree

Example:

1
      1
2
     / \
3
    2   3
4
   / \
5
  4   5

The root node of this tree is 1, node 2 has two child nodes, and nodes 4 and 5 are leaf nodes.

Common goals of binary tree problems:

Core Principle: Step-by-Step Illustration#

1
solve(root) = combine(root.value, solve(root.left), solve(root.right))

1
maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right))

1
      A
2
     / \
3
    B   C

Detailed Algorithm Steps#

Take the “binary tree diameter” as an example. The diameter is the number of edges in the longest path between any two nodes.

Core idea:

1. For each node, calculate the height of the left subtree;
2. Calculate the height of the right subtree;
3. The longest path passing through the current node is leftHeight + rightHeight;
4. Use a global variable to update the maximum value;
5. The current node returns its own height to its parent node.

There is a common distinction here:

• What is returned to the parent node is the “single-side height”;
• What is used to update the answer is the “sum of both left and right sides.”

Many tree DPs have a similar structure: the return value serves the parent node, while the global answer records the optimal result that the current node can form.

TypeScript Implementation#

1
class TreeNode<T> {
2
  constructor(
3
    public value: T,
4
    public left: TreeNode<T> | null = null,
5
    public right: TreeNode<T> | null = null,
6
  ) {}
7
}

1
function maxDepth<T>(root: TreeNode<T> | null): number {
2
  if (root === null) return 0;
3

4
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
5
}

1
function isSymmetric<T>(root: TreeNode<T> | null): boolean {
2
  function isMirror(left: TreeNode<T> | null, right: TreeNode<T> | null): boolean {
3
    if (left === null || right === null) return left === right;
4

5
    return (
6
      left.value === right.value &&
7
      isMirror(left.left, right.right) &&
8
      isMirror(left.right, right.left)
9
    );
10
  }
11

12
  return root === null || isMirror(root.left, root.right);
13
}

1
function diameterOfBinaryTree<T>(root: TreeNode<T> | null): number {
2
  let diameter = 0;
3

4
  function height(node: TreeNode<T> | null): number {
5
    if (node === null) return 0;
6

7
    const left = height(node.left);
8
    const right = height(node.right);
9
    diameter = Math.max(diameter, left + right);
10

11
    return 1 + Math.max(left, right);
12
  }
13

14
  height(root);
15
  return diameter;
16
}

Engineering Optimization: Serialization and Boundary Representation#

If a binary tree needs to be stored in text, transmitted over a network, or kept in a local cache, it must be serialized. The key is to preserve null nodes; otherwise, the structure will be lost.

1
function serialize<T>(root: TreeNode<T> | null): Array<T | null> {
2
  const result: Array<T | null> = [];
3

4
  function dfs(node: TreeNode<T> | null): void {
5
    if (node === null) {
6
      result.push(null);
7
      return;
8
    }
9

10
    result.push(node.value);
11
    dfs(node.left);
12
    dfs(node.right);
13
  }
14

15
  dfs(root);
16
  return result;
17
}

Null node markers are part of the structural information. Without them, many trees of different shapes may produce the same traversal sequence.

Applications and Limitations#

Summary#

• The core model of a binary tree is the root node, left subtree, and right subtree.
• Recursion is the first approach to solving binary tree problems.
• Traversal order determines “when the current node is processed.”
• Tree-shaped problems must distinguish between the information returned to the parent node and the global answer.
• Null nodes are boundaries and also structural information that cannot be ignored during serialization.