PK

PKBytes

Explore tracks
Chapter 24: Tree Fundamentals and Traversal
24.03Intermediate / Advanced6 topics18 min6 interactive animations

Traversal methods

The ways to visit every node of a binary tree: preorder, inorder, postorder, recursive depth-first search, iterative traversals with an explicit stack and level-order breadth-first search.

Learning goals

  • Produce preorder, inorder and postorder sequences by hand and in code
  • Explain how the call stack drives depth-first search
  • Rewrite each depth-first traversal with an explicit stack
  • Traverse by level with a queue

Prerequisites

Binary tree representationStacksQueues

Almost every tree algorithm is a traversal with a small job attached to the visit. Knowing exactly when each node is visited, and what the stack or queue holds at that moment, is the whole skill.

24.03.1

Preorder

**Preorder** visits the node, then its left subtree, then its right subtree. The root always comes first, so a preorder sequence is a natural way to copy or serialise a tree: reading it back creates every parent before its children.

On the tree “1 2 3 4 5 # 6” (root 1 with children 2 and 3; 2 has children 4 and 5; 3 has only a right child 6) preorder is [1, 2, 4, 5, 3, 6]. Step through the “Preorder” preset: each node is output on the way *down*, before either subtree is touched.

Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;
3    out.add(n.val);                              // visit first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h) call stack, h = height

Binary tree traversals: preorder, inorder, postorder and level order

Interactive · edit the input

Your input

Try

binary tree · 6 nodes

1
2
4
5
3
6
Current nodeOn the call stackVisited (in the output)Waiting in the queue

output

none
Setup

Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.

Step 1 / 21
Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

Live state

0 visited

visited

0

No condition evaluated on this step
Execution trace (dry run table)Show 21 steps
StepLineStateWhat happens
1L1visited=0Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.
2L1visited=0 stack depth=1Call preorder(1), the root.
3L3visited=1 stack depth=1Visit 1: before either subtree.
4L1visited=1 stack depth=2Call preorder(2), depth 1.
5L3visited=2 stack depth=2Visit 2: before either subtree.
6L1visited=2 stack depth=3Call preorder(4), depth 2.
7L3visited=3 stack depth=3Visit 4: before either subtree.
8L4visited=3 stack depth=3The left child of 4 is empty, so that call returns at once.
9L5visited=3 stack depth=3The right child of 4 is empty, so that call returns at once.
10L1visited=3 stack depth=3Call preorder(5), depth 2.
11L3visited=4 stack depth=3Visit 5: before either subtree.
12L4visited=4 stack depth=3The left child of 5 is empty, so that call returns at once.
13L5visited=4 stack depth=3The right child of 5 is empty, so that call returns at once.
14L1visited=4 stack depth=2Call preorder(3), depth 1.
15L3visited=5 stack depth=2Visit 3: before either subtree.
16L4visited=5 stack depth=2The left child of 3 is empty, so that call returns at once.
17L1visited=5 stack depth=3Call preorder(6), depth 2.
18L3visited=6 stack depth=3Visit 6: before either subtree.
19L4visited=6 stack depth=3The left child of 6 is empty, so that call returns at once.
20L5visited=6 stack depth=3The right child of 6 is empty, so that call returns at once.
21L1visited=6Preorder: [1, 2, 4, 5, 3, 6].
24.03.2

Inorder

**Inorder** visits the left subtree, then the node, then the right subtree. On a binary search tree this is the keys in **sorted order**, the single most useful fact about BSTs, used in the next chapter for validation, ranking and range queries.

The same tree gives [4, 2, 5, 1, 3, 6]. A node is output only after everything to its left is done; in the “Inorder” preset you can see node 1 wait until the whole left subtree (4, 2, 5) has been emitted.

Java
1static void inorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;
3    inorder(n.left, out);
4    out.add(n.val);                              // visit between the subtrees
5    inorder(n.right, out);
6}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h) call stack

Binary tree traversals: preorder, inorder, postorder and level order

Interactive · edit the input

Your input

Try

binary tree · 6 nodes

1
2
4
5
3
6
Current nodeOn the call stackVisited (in the output)Waiting in the queue

output

none
Setup

Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.

Step 1 / 21
Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

Live state

0 visited

visited

0

No condition evaluated on this step
Execution trace (dry run table)Show 21 steps
StepLineStateWhat happens
1L1visited=0Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.
2L1visited=0 stack depth=1Call preorder(1), the root.
3L3visited=1 stack depth=1Visit 1: before either subtree.
4L1visited=1 stack depth=2Call preorder(2), depth 1.
5L3visited=2 stack depth=2Visit 2: before either subtree.
6L1visited=2 stack depth=3Call preorder(4), depth 2.
7L3visited=3 stack depth=3Visit 4: before either subtree.
8L4visited=3 stack depth=3The left child of 4 is empty, so that call returns at once.
9L5visited=3 stack depth=3The right child of 4 is empty, so that call returns at once.
10L1visited=3 stack depth=3Call preorder(5), depth 2.
11L3visited=4 stack depth=3Visit 5: before either subtree.
12L4visited=4 stack depth=3The left child of 5 is empty, so that call returns at once.
13L5visited=4 stack depth=3The right child of 5 is empty, so that call returns at once.
14L1visited=4 stack depth=2Call preorder(3), depth 1.
15L3visited=5 stack depth=2Visit 3: before either subtree.
16L4visited=5 stack depth=2The left child of 3 is empty, so that call returns at once.
17L1visited=5 stack depth=3Call preorder(6), depth 2.
18L3visited=6 stack depth=3Visit 6: before either subtree.
19L4visited=6 stack depth=3The left child of 6 is empty, so that call returns at once.
20L5visited=6 stack depth=3The right child of 6 is empty, so that call returns at once.
21L1visited=6Preorder: [1, 2, 4, 5, 3, 6].
24.03.3

Postorder

**Postorder** visits both subtrees and then the node. Children are always handled before their parent, which is what you need when a node's answer depends on its children's answers: heights, sizes, sums, deleting a tree, evaluating an expression tree.

The sequence for the sample tree is [4, 5, 2, 6, 3, 1]: the root comes last. Most of the structural computations in this chapter are postorder in disguise: the function returns a value for the subtree and the parent combines them.

Java
1static void postorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;
3    postorder(n.left, out);
4    postorder(n.right, out);
5    out.add(n.val);                              // visit last
6}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h) call stack

Binary tree traversals: preorder, inorder, postorder and level order

Interactive · edit the input

Your input

Try

binary tree · 6 nodes

1
2
4
5
3
6
Current nodeOn the call stackVisited (in the output)Waiting in the queue

output

none
Setup

Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.

Step 1 / 21
Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

Live state

0 visited

visited

0

No condition evaluated on this step
Execution trace (dry run table)Show 21 steps
StepLineStateWhat happens
1L1visited=0Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.
2L1visited=0 stack depth=1Call preorder(1), the root.
3L3visited=1 stack depth=1Visit 1: before either subtree.
4L1visited=1 stack depth=2Call preorder(2), depth 1.
5L3visited=2 stack depth=2Visit 2: before either subtree.
6L1visited=2 stack depth=3Call preorder(4), depth 2.
7L3visited=3 stack depth=3Visit 4: before either subtree.
8L4visited=3 stack depth=3The left child of 4 is empty, so that call returns at once.
9L5visited=3 stack depth=3The right child of 4 is empty, so that call returns at once.
10L1visited=3 stack depth=3Call preorder(5), depth 2.
11L3visited=4 stack depth=3Visit 5: before either subtree.
12L4visited=4 stack depth=3The left child of 5 is empty, so that call returns at once.
13L5visited=4 stack depth=3The right child of 5 is empty, so that call returns at once.
14L1visited=4 stack depth=2Call preorder(3), depth 1.
15L3visited=5 stack depth=2Visit 3: before either subtree.
16L4visited=5 stack depth=2The left child of 3 is empty, so that call returns at once.
17L1visited=5 stack depth=3Call preorder(6), depth 2.
18L3visited=6 stack depth=3Visit 6: before either subtree.
19L4visited=6 stack depth=3The left child of 6 is empty, so that call returns at once.
20L5visited=6 stack depth=3The right child of 6 is empty, so that call returns at once.
21L1visited=6Preorder: [1, 2, 4, 5, 3, 6].
24.03.4

Recursive DFS

The three orders are all **depth-first search**: follow one branch to the bottom before trying the next. The recursion makes the call stack remember the path from the root to the current node, which the animation draws as the list of active calls. They differ only in *where* the visit happens relative to the two recursive calls.

The stack depth is the tree's height, plus one frame for the null call. For a balanced tree that is about log n, but for a degenerate tree with n nodes it is n, and a deep enough chain overflows Java's thread stack. That is the reason to learn the iterative versions in the next lesson.

OrderVisit happensTypical use
Preorderbefore the subtreescopy a tree, serialise, prefix expressions
Inorderbetween the subtreessorted keys of a BST
Postorderafter the subtreesheights, sizes, deleting, postfix expressions

Binary tree traversals: preorder, inorder, postorder and level order

Interactive · edit the input

Your input

Try

binary tree · 6 nodes

1
2
4
5
3
6
Current nodeOn the call stackVisited (in the output)Waiting in the queue

output

none
Setup

Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.

Step 1 / 21
Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

Live state

0 visited

visited

0

No condition evaluated on this step
Execution trace (dry run table)Show 21 steps
StepLineStateWhat happens
1L1visited=0Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.
2L1visited=0 stack depth=1Call preorder(1), the root.
3L3visited=1 stack depth=1Visit 1: before either subtree.
4L1visited=1 stack depth=2Call preorder(2), depth 1.
5L3visited=2 stack depth=2Visit 2: before either subtree.
6L1visited=2 stack depth=3Call preorder(4), depth 2.
7L3visited=3 stack depth=3Visit 4: before either subtree.
8L4visited=3 stack depth=3The left child of 4 is empty, so that call returns at once.
9L5visited=3 stack depth=3The right child of 4 is empty, so that call returns at once.
10L1visited=3 stack depth=3Call preorder(5), depth 2.
11L3visited=4 stack depth=3Visit 5: before either subtree.
12L4visited=4 stack depth=3The left child of 5 is empty, so that call returns at once.
13L5visited=4 stack depth=3The right child of 5 is empty, so that call returns at once.
14L1visited=4 stack depth=2Call preorder(3), depth 1.
15L3visited=5 stack depth=2Visit 3: before either subtree.
16L4visited=5 stack depth=2The left child of 3 is empty, so that call returns at once.
17L1visited=5 stack depth=3Call preorder(6), depth 2.
18L3visited=6 stack depth=3Visit 6: before either subtree.
19L4visited=6 stack depth=3The left child of 6 is empty, so that call returns at once.
20L5visited=6 stack depth=3The right child of 6 is empty, so that call returns at once.
21L1visited=6Preorder: [1, 2, 4, 5, 3, 6].
24.03.5

Iterative stack traversals

An iterative traversal keeps the stack the recursion kept implicitly. **Preorder**: push the root; pop a node, visit it, push its right child and then its left, so that the left is popped first. **Inorder**: go left as far as possible pushing every node; pop one and visit it; then continue from its right child. **Postorder** is the awkward one: either run a modified preorder (node, right, left) and reverse the output, or track the last visited node to know when a node's right subtree is finished.

The animation “Iterative tree traversal” (from the stack chapter) shows the stack contents at each step for all three; the stack never holds more than the tree's height plus one node, so the space is O(h).

Java
1static List<Integer> preorderIter(TreeNode root) {
2    List<Integer> out = new ArrayList<>();
3    Deque<TreeNode> stack = new ArrayDeque<>();
4    if (root != null) stack.push(root);
5    while (!stack.isEmpty()) {
6        TreeNode n = stack.pop();
7        out.add(n.val);
8        if (n.right != null) stack.push(n.right);    // pushed first, so popped last
9        if (n.left != null) stack.push(n.left);
10    }
11    return out;
12}
13
14static List<Integer> inorderIter(TreeNode root) {
15    List<Integer> out = new ArrayList<>();
16    Deque<TreeNode> stack = new ArrayDeque<>();
17    TreeNode cur = root;
18    while (cur != null || !stack.isEmpty()) {
19        while (cur != null) { stack.push(cur); cur = cur.left; }   // walk down the left spine
20        cur = stack.pop();
21        out.add(cur.val);
22        cur = cur.right;
23    }
24    return out;
25}
26
27static List<Integer> postorderIter(TreeNode root) {
28    LinkedList<Integer> out = new LinkedList<>();
29    Deque<TreeNode> stack = new ArrayDeque<>();
30    if (root != null) stack.push(root);
31    while (!stack.isEmpty()) {
32        TreeNode n = stack.pop();
33        out.addFirst(n.val);                         // node, right, left, built backwards
34        if (n.left != null) stack.push(n.left);
35        if (n.right != null) stack.push(n.right);
36    }
37    return out;
38}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Depth-first traversal with an explicit stack

Interactive · edit the input

Your input

Try

Heap as a binary tree · 7 nodes

1
0
2
1
3
2
4
3
5
4
6
5
7
6

1, 2, 3, 4, 5, 6, 7

int[] arr · length 7

1
2
3
4
5
6
7
0123456
Current nodeOn the stackVisited

stack of node indexes (top is last)

empty

visit order

none yet
Setup

Inorder visits the left subtree, the node, then the right subtree. The stack replaces the call stack that recursion would use.

Step 1 / 16
Java
1// nodes are array indexes: children of i are 2i + 1 and 2i + 2
2// preorder: node, left, right. Push right first so left is popped first.
3Deque<Integer> st = new ArrayDeque<>(); st.push(0);
4while (!st.isEmpty()) { int i = st.pop(); visit(i); if (2*i+2 < n) st.push(2*i+2); if (2*i+1 < n) st.push(2*i+1); }
5// inorder: left, node, right. Walk left, remember the path on the stack.
6int cur = 0;  while (cur < n || !st.isEmpty()) {
7    while (cur < n) { st.push(cur); cur = 2*cur + 1; }          // go as far left as possible
8    int i = st.pop(); visit(i); cur = 2*i + 2;                  // then the right subtree
9}
10// postorder: left, right, node. Visit a node only after its right child was visited.
11int last = -1; cur = 0; while (cur < n || !st.isEmpty()) {
12    if (cur < n) { st.push(cur); cur = 2*cur + 1; }
13    else { int top = st.peek(), r = 2*top + 2;
14           if (r < n && last != r) cur = r; else { visit(top); last = st.pop(); } }
15}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 16 steps
StepLineStateWhat happens
1L6Inorder visits the left subtree, the node, then the right subtree. The stack replaces the call stack that recursion would use.
2L7cur=1Push 1 and keep going left.
3L7cur=2Push 2 and keep going left.
4L7cur=4Push 4 and keep going left.
5L8visit=4No left child left: pop 4 and visit it, then move to its right subtree.
6L8visit=2No left child left: pop 2 and visit it, then move to its right subtree.
7L7cur=5Push 5 and keep going left.
8L8visit=5No left child left: pop 5 and visit it, then move to its right subtree.
9L8visit=1No left child left: pop 1 and visit it, then move to its right subtree.
10L7cur=3Push 3 and keep going left.
11L7cur=6Push 6 and keep going left.
12L8visit=6No left child left: pop 6 and visit it, then move to its right subtree.
13L8visit=3No left child left: pop 3 and visit it, then move to its right subtree.
14L7cur=7Push 7 and keep going left.
15L8visit=7No left child left: pop 7 and visit it, then move to its right subtree.
16L9return=[4, 2, 5, 1, 6, 3, 7]Inorder: [4, 2, 5, 1, 6, 3, 7]. The stack never holds more than the tree height plus one: O(h) space.
24.03.6

Level-order BFS

**Level order** visits nodes by depth: the root, then its children, then the grandchildren. It is **breadth-first search** and uses a **queue**: take the oldest node, visit it, add its children at the back. On the sample tree the result is [1, 2, 3, 4, 5, 6].

The queue holds at most one level plus part of the next, so the space is O(w) for width w, which for a balanced tree is about n / 2 at the bottom level. Depth-first uses O(h) and breadth-first O(w); which is smaller depends on the shape. The next lesson group builds all the 'by level' and 'view' problems on this loop.

Java
1static List<Integer> levelOrder(TreeNode root) {
2    List<Integer> out = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        TreeNode n = queue.poll();                   // oldest first
7        out.add(n.val);
8        if (n.left != null) queue.add(n.left);
9        if (n.right != null) queue.add(n.right);
10    }
11    return out;
12}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(w), w = widest level

Binary tree traversals: preorder, inorder, postorder and level order

Interactive · edit the input

Your input

Try

binary tree · 6 nodes

1
2
4
5
3
6
Current nodeOn the call stackVisited (in the output)Waiting in the queue

output

none
Setup

Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.

Step 1 / 21
Java
1static void preorder(TreeNode n, List<Integer> out) {
2    if (n == null) return;                       // empty subtree: nothing to visit
3    out.add(n.val);                              // visit the node first
4    preorder(n.left, out);
5    preorder(n.right, out);
6}
7static void inorder(TreeNode n, List<Integer> out) {
8    if (n == null) return;
9    inorder(n.left, out);
10    out.add(n.val);                              // visit between the two subtrees
11    inorder(n.right, out);
12}
13static void postorder(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    postorder(n.left, out);
16    postorder(n.right, out);
17    out.add(n.val);                              // visit after both subtrees
18}
19static List<Integer> levelOrder(TreeNode root) {
20    List<Integer> out = new ArrayList<>();
21    Deque<TreeNode> queue = new ArrayDeque<>();
22    if (root != null) queue.add(root);
23    while (!queue.isEmpty()) {
24        TreeNode n = queue.poll();               // oldest node first
25        out.add(n.val);
26        if (n.left != null) queue.add(n.left);
27        if (n.right != null) queue.add(n.right);
28    }
29    return out;
30}

Live state

0 visited

visited

0

No condition evaluated on this step
Execution trace (dry run table)Show 21 steps
StepLineStateWhat happens
1L1visited=0Preorder traversal of a tree with 6 nodes. The recursion's call stack remembers the path back to the root.
2L1visited=0 stack depth=1Call preorder(1), the root.
3L3visited=1 stack depth=1Visit 1: before either subtree.
4L1visited=1 stack depth=2Call preorder(2), depth 1.
5L3visited=2 stack depth=2Visit 2: before either subtree.
6L1visited=2 stack depth=3Call preorder(4), depth 2.
7L3visited=3 stack depth=3Visit 4: before either subtree.
8L4visited=3 stack depth=3The left child of 4 is empty, so that call returns at once.
9L5visited=3 stack depth=3The right child of 4 is empty, so that call returns at once.
10L1visited=3 stack depth=3Call preorder(5), depth 2.
11L3visited=4 stack depth=3Visit 5: before either subtree.
12L4visited=4 stack depth=3The left child of 5 is empty, so that call returns at once.
13L5visited=4 stack depth=3The right child of 5 is empty, so that call returns at once.
14L1visited=4 stack depth=2Call preorder(3), depth 1.
15L3visited=5 stack depth=2Visit 3: before either subtree.
16L4visited=5 stack depth=2The left child of 3 is empty, so that call returns at once.
17L1visited=5 stack depth=3Call preorder(6), depth 2.
18L3visited=6 stack depth=3Visit 6: before either subtree.
19L4visited=6 stack depth=3The left child of 6 is empty, so that call returns at once.
20L5visited=6 stack depth=3The right child of 6 is empty, so that call returns at once.
21L1visited=6Preorder: [1, 2, 4, 5, 3, 6].

Practice ladder

Now try it yourself

Easy

  • Binary Tree Preorder Traversal
  • Binary Tree Inorder Traversal
  • Binary Tree Postorder Traversal

Medium

  • Binary Tree Level Order Traversal
  • Kth Smallest Element in a BST

Advanced

  • Binary Tree Postorder Traversal (one stack)
  • Morris Inorder Traversal

Key takeaways

  • Preorder, inorder and postorder differ only in where the visit sits relative to the two recursive calls.
  • Inorder on a BST is sorted; postorder handles children before parents.
  • Recursive DFS uses stack space equal to the tree height, which is n for a chain.
  • Explicit stacks rewrite DFS iteratively; a queue gives level order.