Recursive Binary Tree Traversal Methods

Welcome back! In our last lesson, we established the fundamental concepts of binary trees, defining their structure and terminology, and learning how to represent them in TypeScript. We now have the tools to build a tree. Today, we'll learn how to navigate it.

The process of visiting each node in a tree in a specific, predictable order is called traversal. Unlike linear structures like arrays, trees can be traversed in several meaningful ways. This lesson focuses on the three most common recursive depth-first traversals: preorder, inorder, and postorder. Mastering these patterns is the key to solving a vast range of tree-based problems.

Your experience with the DOM has given you an intuitive sense of traversing a hierarchical structure. Here, we'll formalize that intuition into powerful, general-purpose algorithms.

Depth-First Search: The Core Idea

The three traversals we're learning today are all forms of Depth-First Search (DFS). The name says it all: the strategy is to go as deep as possible down one path before backtracking and exploring another. Imagine navigating a maze by always taking the leftmost path until you hit a dead end, then backtracking to the last junction and trying the next available path. That's the essence of DFS.

For any given node in a binary tree, we have three fundamental actions we can perform:

1. Visit the node itself (e.g., read or print its value).
2. Recursively traverse its left subtree.
3. Recursively traverse its right subtree.

The difference between preorder, inorder, and postorder traversal is simply the sequence in which these three actions are performed.

The Three Traversal Orders: Preorder, Inorder, and Postorder

A simple mnemonic can help you remember these patterns: the prefix (pre, in, post) tells you where the "visit" action happens relative to the traversal of the left and right subtrees.

• Preorder (Root → Left → Right): Visit the current node before traversing its children.
• Inorder (Left → Root → Right): Visit the current node in between traversing its left and right children.
• Postorder (Left → Right → Root): Visit the current node after traversing its children.

The following image provides an excellent summary of these three traversals, showing the rule, the resulting node order, and the recursive pseudocode for each.

Now, let's dive into each one with code and a detailed visualization. We'll use the TreeNode class from our previous lesson:

class TreeNode {
    value: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(value: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

Preorder Traversal (Root → Left → Right)

In preorder traversal, we process the current node first, then recursively traverse the left subtree, and finally the right subtree. This is useful for tasks like creating an exact copy of a tree, as you can create the parent node before its children.

The recursive implementation is very direct.

function preorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (node === null) {
            return;
        }
        // 1. Visit the current node
        result.push(node.value);
        // 2. Traverse the left subtree
        traverse(node.left);
        // 3. Traverse the right subtree
        traverse(node.right);
    }

    traverse(root);
    return result;
}

To truly understand how the recursion unfolds, it's essential to visualize the call stack. The following video provides a brilliant, step-by-step animation of preorder traversal, showing how nodes are pushed onto and popped off the call stack.

Inorder Traversal (Left → Root → Right)

Inorder traversal is perhaps the most well-known. It traverses the left subtree, visits the current node, and then traverses the right subtree. Its most famous application is with Binary Search Trees (BSTs), where an inorder traversal visits the nodes in sorted order. We will explore BSTs in a future lesson, but the traversal pattern itself is fundamental.

The implementation is just a reordering of the lines from our preorder function.

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (node === null) {
            return;
        }
        // 1. Traverse the left subtree
        traverse(node.left);
        // 2. Visit the current node
        result.push(node.value);
        // 3. Traverse the right subtree
        traverse(node.right);
    }

    traverse(root);
    return result;
}

Again, let's visualize the call stack to see this in action. The recursive calls must go all the way down the left-most path before the first value is ever printed.

Postorder Traversal (Left → Right → Root)

In postorder traversal, we visit the current node last, after recursively traversing both its left and right subtrees. This "bottom-up" approach is useful when you need to operate on a node's children before the node itself. A classic example is deleting nodes in a tree: you must delete the children before you can delete their parent.

function postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
        if (node === null) {
            return;
        }
        // 1. Traverse the left subtree
        traverse(node.left);
        // 2. Traverse the right subtree
        traverse(node.right);
        // 3. Visit the current node
        result.push(node.value);
    }

    traverse(root);
    return result;
}

Let's complete our viewing with the postorder visualization. You'll see that a node's value is added to the output only after the execution for both of its subtrees has fully completed.

An Intuitive Visualization

While understanding the call stack is crucial, sometimes a quick visual trick can help you trace traversals on a whiteboard. Imagine drawing an outline around the tree, starting from the left of the root and moving counter-clockwise.

• Preorder: Mark a node the first time you pass it on its left side. (Green arrow)
• Inorder: Mark a node the second time you pass it from underneath. (Blue arrow)
• Postorder: Mark a node the third and final time you pass it on its right side. (Red arrow)

The following video demonstrates this trick very effectively.

Reviewing the Code Structure

For a clear summary of the recursive JavaScript code for all three methods, this article from Hackernoon is a useful reference. The structure is identical to the TypeScript versions we've discussed.

Conclusion

In this lesson, you've learned the three fundamental depth-first traversal algorithms for binary trees. These patterns are not just academic exercises; they form the backbone of countless more complex tree algorithms.

Here are the key takeaways:

• Depth-First Search (DFS) explores as deep as possible down one path before backtracking.
• The three main recursive DFS traversals—preorder, inorder, and postorder—are defined by when the current node is "visited" relative to its children.
  • Preorder: Root → Left → Right
  • Inorder: Left → Root → Right
  • Postorder: Left → Right → Root
• Recursion provides a natural and elegant way to implement these traversals, directly mirroring the recursive definition of a tree itself.

We have focused on exploring the tree "deeply." In our next lesson, we will cover the other major traversal strategy: Breadth-First Search (BFS), which explores the tree "widely," level by level, using a queue.