Overview#

Recursive traversal is the foundation for understanding binary trees. The difference between preorder, inorder, and postorder traversal is not which nodes are visited, but “when the current node is processed.”

The three orders are:

• Preorder: process the current node first, then process the left and right subtrees;
• Inorder: process the left subtree first, then the current node, and finally the right subtree;
• Postorder: process the left and right subtrees first, and finally the current node.

Once you master these three orders, many tree problems can be transformed into choosing the appropriate processing timing.

Prerequisites

• Recursive call stack: stores the current node and return position
• Binary tree structure: traversal order revolves around root, left, and right
• Visit timing: preorder, inorder, and postorder differ only in where the current node is processed

Problem Definition#

Given a binary tree:

1
      A
2
     / \
3
    B   C
4
   / \
5
  D   E

The different traversal results are as follows:

The essence of traversal is: every node passes through three key positions.

1
Before entering the node
2
After finishing the left subtree
3
After finishing the right subtree

Whichever position you place the “visit current node” statement in, you get the corresponding traversal.

Core Principle: Step-by-Step Diagram#

A recursive function can be written as a unified framework:

1
function traverse(node: TreeNode | null): void {
2
  if (node === null) return;
3

4
  //Pre-order position
5
  traverse(node.left);
6
  //In-order position
7
  traverse(node.right);
8
  //Post-order position
9
}

Detailed Algorithm Steps#

When writing recursive traversal, you can think in the following order:

1. How empty nodes are handled;
2. Whether the current node should be visited in the preorder, inorder, or postorder position;
3. Whether state needs to be passed down as parameters;
4. Whether return values need to be collected upward from subtrees;
5. Whether the recursion depth may become too large.

The advantage of recursion is that the code stays close to the definition of the tree; the disadvantage is that the call stack is maintained by the runtime, and extremely deep trees may cause a stack overflow.

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 preorder<T>(root: TreeNode<T> | null): T[] {
2
  const result: T[] = [];
3

4
  function dfs(node: TreeNode<T> | null): void {
5
    if (node === null) return;
6

7
    result.push(node.value);
8
    dfs(node.left);
9
    dfs(node.right);
10
  }
11

12
  dfs(root);
13
  return result;
14
}

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

4
  function dfs(node: TreeNode<T> | null): void {
5
    if (node === null) return;
6

7
    dfs(node.left);
8
    result.push(node.value);
9
    dfs(node.right);
10
  }
11

12
  dfs(root);
13
  return result;
14
}

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

4
  function dfs(node: TreeNode<T> | null): void {
5
    if (node === null) return;
6

7
    dfs(node.left);
8
    dfs(node.right);
9
    result.push(node.value);
10
  }
11

12
  dfs(root);
13
  return result;
14
}

Engineering Optimization: Converting Recursion to Iteration#

Recursion relies on the call stack. If the tree may be very deep, you can explicitly use a stack to simulate traversal.

1
function preorderIterative<T>(root: TreeNode<T> | null): T[] {
2
  if (root === null) return [];
3

4
  const result: T[] = [];
5
  const stack: TreeNode<T>[] = [root];
6

7
  while (stack.length > 0) {
8
    const node = stack.pop()!;
9
    result.push(node.value);
10

11
    if (node.right) stack.push(node.right);
12
    if (node.left) stack.push(node.left);
13
  }
14

15
  return result;
16
}

Because the stack is last-in, first-out, you must push the right child first and then the left child to ensure that the left subtree is processed first.

Applications and Limitations#

Summary#

• The difference between preorder, inorder, and postorder is where the current node is processed.
• The binary tree recursion framework can unify all three traversals.
• Preorder is suitable for top-down, inorder is suitable for BSTs, and postorder is suitable for bottom-up.
• For deep tree scenarios, recursion can be rewritten using an explicit stack.