Tree traversal Algorithms

A tree is a collection of nodes connected by edges. Traversal means visiting every node exactly once. The question is: in what order?

Three depth-first strategies exist. The difference is when you process the current node relative to its children.

• Preorder: Process the node, then left, then right. Good for copying a tree.
• Inorder: Left, then the node, then right. On a binary search tree, this gives you sorted order.
• Postorder: Left, then right, then the node. Good for deleting a tree (children first, parent last).

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function preorder(node, result = []) {
    if (!node) return result;
    result.push(node.value);
    preorder(node.left, result);
    preorder(node.right, result);
    return result;
}

function inorder(node, result = []) {
    if (!node) return result;
    inorder(node.left, result);
    result.push(node.value);
    inorder(node.right, result);
    return result;
}

function postorder(node, result = []) {
    if (!node) return result;
    postorder(node.left, result);
    postorder(node.right, result);
    result.push(node.value);
    return result;
}

Complexity (all three)

• Time: O(n) — every node visited once.
• Space: O(h) — recursion stack depth equals the tree height. O(log n) for balanced trees, O(n) for skewed ones.

The one people forget: level-order

There's a fourth traversal that uses a queue instead of recursion. It visits nodes level by level, left to right. Useful for finding the shortest path or printing a tree by depth.

function levelOrder(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node.value);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }

    return result;
}

Time: O(n). Space: O(w) where w is the maximum width of the tree.

When to use which

Pick the traversal based on what you need. Sorted output from a BST? Inorder. Serialize a tree for reconstruction? Preorder. Evaluate an expression tree? Postorder. Find nodes at a specific depth? Level-order.