# Tree Traversals — Preorder, Inorder, Postorder and Level Order

Source: https://skills101.in/learn/dsa/dsa-tree-traversals — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

A **binary tree** is made of nodes; each node has a value and up to two children, `left` and `right`. Almost every tree problem — height, sum, mirror, path, serialise, validate a BST — is "visit every node in the **right order** and do something". There are four orders worth knowing by heart.

## 1. One tree, four orders

![A binary tree with root 1, children 2 and 3, node 2 has children 4 and 5, node 3 has right child 6; preorder is 1 2 4 5 3 6, inorder 4 2 5 1 3 6, postorder 4 5 2 6 3 1, level order 1 2 3 4 5 6](https://skills101.in/learn-img/dsa/tree-traversals.svg)

The three **depth-first** orders all go left before right. They differ only in **when the root is visited**:

- **Preorder** — root, left, right. (Root first: copying a tree, printing a folder structure.)
- **Inorder** — left, root, right. (In a binary **search** tree this gives the values **sorted**.)
- **Postorder** — left, right, root. (Root last: deleting a tree, computing sizes and heights from the children up.)

**Level order** is breadth-first: level by level, left to right, using a **queue**.

## 2. Recursive traversals

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

def preorder(n, out):
    if n:
        out.append(n.val); preorder(n.left, out); preorder(n.right, out)
    return out

def inorder(n, out):
    if n:
        inorder(n.left, out); out.append(n.val); inorder(n.right, out)
    return out

def postorder(n, out):
    if n:
        postorder(n.left, out); postorder(n.right, out); out.append(n.val)
    return out

print(preorder(root, []))
print(inorder(root, []))
print(postorder(root, []))
```

```text
[1, 2, 4, 5, 3, 6]
[4, 2, 5, 1, 3, 6]
[4, 5, 2, 6, 3, 1]
```

Every node is visited once: **O(n)** time. The recursion uses **O(h)** stack space, where `h` is the height — O(log n) for a balanced tree, but O(n) for a tree that is one long chain.

## 3. Level order (BFS)

Take nodes from the front of a queue; add their children at the back. Process **one level at a time** by reading the queue's length at the start of each level.

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))   # the tree in the diagram

from collections import deque

def level_order(root):
    levels, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):          # exactly the nodes of this level
            n = q.popleft()
            level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        levels.append(level)
    return levels

print(level_order(root))
print([lvl[-1] for lvl in level_order(root)])     # right side view
```

```text
[[1], [2, 3], [4, 5, 6]]
[1, 3, 6]
```

Many problems are tiny changes to this loop: **right side view** (last of each level), **level averages**, **zigzag order** (reverse every other level), **minimum depth** (stop at the first leaf).

## 4. Iterative traversals with an explicit stack

Interviewers sometimes forbid recursion (or the tree is so deep that recursion would overflow). Inorder with a stack: go **left** as far as possible, pushing nodes; then pop one, visit it, and move to its **right** child.

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))   # the tree in the diagram

def inorder_iterative(root):
    out, stack, n = [], [], root
    while n or stack:
        while n:                 # go as far left as possible
            stack.append(n)
            n = n.left
        n = stack.pop()
        out.append(n.val)        # visit
        n = n.right              # then the right subtree
    return out

def preorder_iterative(root):
    out, stack = [], [root] if root else []
    while stack:
        n = stack.pop()
        out.append(n.val)
        if n.right: stack.append(n.right)    # push right first, so left is popped first
        if n.left: stack.append(n.left)
    return out

print(inorder_iterative(root))
print(preorder_iterative(root))
```

```text
[4, 2, 5, 1, 3, 6]
[1, 2, 4, 5, 3, 6]
```

## 5. Postorder thinking: answers built from the children

Many questions are "compute something for each node **from its children's answers**" — that is postorder. Height is the classic:

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))   # the tree in the diagram

def height(n):
    if not n:
        return 0
    return 1 + max(height(n.left), height(n.right))

def count_leaves(n):
    if not n:
        return 0
    if not n.left and not n.right:
        return 1
    return count_leaves(n.left) + count_leaves(n.right)

print(height(root), count_leaves(root))
```

```text
3 3
```

The same shape solves diameter, balanced-tree check, maximum path sum and subtree sums: get the left answer, get the right answer, combine at the node.

### Inorder and level order in Java

```java
import java.util.*;

public class Main {
    static class Node {
        int val; Node left, right;
        Node(int v, Node l, Node r) { val = v; left = l; right = r; }
        Node(int v) { this(v, null, null); }
    }

    static void inorder(Node n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out); out.add(n.val); inorder(n.right, out);
    }

    static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> levels = new ArrayList<>();
        Queue<Node> q = new ArrayDeque<>();
        if (root != null) q.offer(root);
        while (!q.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int size = q.size(); size > 0; size--) {
                Node n = q.poll();
                level.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
        List<Integer> in = new ArrayList<>();
        inorder(root, in);
        System.out.println(in);
        System.out.println(levelOrder(root));
    }
}
```

```text
[4, 2, 5, 1, 3, 6]
[[1], [2, 3], [4, 5, 6]]
```

## 6. Which traversal for which problem?

| Problem | Traversal |
|---|---|
| Print a BST in sorted order, k-th smallest, validate a BST | inorder |
| Copy / serialise a tree, print a directory tree | preorder |
| Height, diameter, delete a tree, subtree sums | postorder |
| Level averages, right side view, minimum depth, zigzag | level order (BFS) |

## Common mistakes

- Forgetting the base case `if not n` — the recursion crashes on `None`.
- Taking `len(q)` **inside** the inner loop in level order — the queue grows while you loop, so levels mix. Read it once per level.
- In iterative preorder, pushing the left child first — then the right subtree is visited first.
- Assuming recursion depth is fine for 10⁵ nodes in a chain — Python's default limit is about 1000; use an iterative version.

## Quick recap

- Preorder = root, left, right; inorder = left, root, right; postorder = left, right, root.
- Level order = BFS with a queue, one level per outer loop.
- All four are O(n) time; recursion uses O(h) extra space.
- Inorder of a BST is sorted; postorder builds answers from the children up.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-tree-traversals