---
title: "Tree traversal"
url: https://algopath.pro/patterns/tree-traversal
language: en
summary: "Visit every node of the tree exactly once. Where exactly you place the visit is what decides what the traversal computes."
updated: 2026-08-24
---

# Tree traversal

Visit every node of the tree exactly once. Where exactly you place the visit is what decides what the traversal computes.

## 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.

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

## When should you use Tree traversal?

- 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.

## What is the time and space complexity of Tree traversal?

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

## 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.

```javascript
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;
}
```

## 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.

## JavaScript

```javascript
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;
}
```

## Python

```python
def traverse(node, result=None):
    if result is None:
        result = []
    if not node:
        return result
    traverse(node.left, result)
    result.append(node.val)  # inorder here; move this line for pre/post
    traverse(node.right, result)
    return result
```

## PHP

```php
function traverse(?TreeNode $node, array &$result = []): array {
    if ($node === null) return $result;
    traverse($node->left, $result);
    $result[] = $node->val; // inorder here; move this line for pre/post
    traverse($node->right, $result);
    return $result;
}
```