Skills101

AdvancedData Structures & Algorithms · Lesson 25 of 25 · Updated ·

Tree Traversals — Preorder, Inorder, Postorder and Level Order

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

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

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, []))
[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.

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

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))
[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:

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

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));
    }
}
[4, 2, 5, 1, 3, 6]
[[1], [2, 3], [4, 5, 6]]

6. Which traversal for which problem?

ProblemTraversal
Print a BST in sorted order, k-th smallest, validate a BSTinorder
Copy / serialise a tree, print a directory treepreorder
Height, diameter, delete a tree, subtree sumspostorder
Level averages, right side view, minimum depth, zigzaglevel 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 what you learned

📝 Quiz: Tree Traversals5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →