Tree traversal

How does Tree traversal work?

Every traversal does the same two things at a node. It visits the node and descends into each child.

Pre-order visits the node before its children. Use it when the parent's value is needed first.

In-order visits the left child, then the node, then the right. On a search tree that yields sorted order.

Post-order visits both children before the node. Use it when the answer depends on the children.

Level-order uses a queue instead of recursion. It works in rows rather than in depth.

Only the position of the visit changes. The walking part is identical in all of them.

1. root 1, children 2 and 3The root is reached first, whatever the order.
2. pre-order: 1, 2, 3The node is recorded, then both of its children.
3. in-order: 2, 1, 3The left child is recorded before the node itself.
4. post-order: 2, 3, 1Both children finish before the node is recorded.
5. level-order: 1, 2, 3A queue reads row by row instead of going deep.

function traverse(node, result = []) {
    if (!node) return result; // base case
    traverse(node.left, result);
    result.push(node.val); // inorder here; move this line for pre/post
    traverse(node.right, result);
    return result;
}

A worked example of Tree traversal

Diameter of a binary tree

Return the longest path between any two nodes, counted in edges.

The path does not have to pass through the root.

At any node, the best local path is the left depth plus the right depth.

So compute the depth in post-order. Record the best sum while the calls unwind.

function diameterOfBinaryTree(root) {
    let best = 0;

    function depth(node) {
        if (!node) return 0;

        const left = depth(node.left);
        const right = depth(node.right);

        // the path passing through this node, counted in edges
        best = Math.max(best, left + right);

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

    depth(root);
    return best;
}

When should you use Tree traversal?

These phrases in a problem statement point here:

• •binary tree given as a root node with left/right pointers
• •visit every node (preorder / inorder / postorder / level-order)
• •compute a depth, height, or sum over the whole tree
• •process children before or after the parent
• •level-by-level output (BFS with a queue)

What is Tree traversal confused with?

• Graph BFS / DFS: A graph can reach a node twice, so it needs a visited set. A tree cannot, so it does not.
• Recursion: Recursion is how a traversal is usually written. This page is about the three visit orders.
• Stack (LIFO): An iterative traversal swaps the call stack for your own. The visiting order stays the same.
• Binary search tree: In a search tree, in-order gives sorted values. In any other tree that order means nothing.

Common mistakes with Tree traversal

• Missing the empty-node check

  Every recursion has to stop at an empty child. That check is the base case.

• Putting the visit in the wrong place

  The visit line is the only difference between the orders. Moving it changes the answer.

• Pushing children in the wrong order

  An iterative pre-order pushes the right child first. A stack reverses whatever you give it.

• Recursing down a very deep tree

  A million nodes in one chain overflows the call stack. Use an explicit stack there.

Which interview problems use Tree traversal?

• Binary tree inorder traversal: The plain form, recursive or with a stack.
• Maximum depth of a binary tree: One plus the deeper of the two children.
• Diameter of a binary tree: Left depth plus right depth at every node.
• Binary tree level order traversal: A queue, processing one row per round.
• Path sum: Carry the running total down the tree.
• Invert a binary tree: Swap the two children at every node.
• Binary tree right side view: The last node reached on each level.

What is the time and space complexity of Tree traversal?

O(n)

n nodes give O(n) time. Space is O(h) for the stack, and h equals n on a chain.