PK

PKBytes

Explore tracks
Chapter 24: Tree Fundamentals and Traversal
24.04Intermediate / Advanced6 topics17 min6 interactive animations

Level and view problems

Problems that group or project a tree by level or column: level order lists, zigzag traversal, left and right views, top and bottom views and vertical order.

Learning goals

  • Return nodes grouped by level with the size-snapshot trick
  • Reverse alternate levels for zigzag order
  • Read the visible nodes from the left, right, top and bottom
  • Assign columns to nodes and group them for vertical order

Prerequisites

Traversal methods

These problems ask what you would see when looking at a tree from a side, or how the nodes arrange by depth and column. One breadth-first loop, plus a column number when needed, answers all of them.

24.04.1

Level order

To return the nodes **grouped by level**, take a snapshot of the queue's size at the start of each round: that many nodes belong to the current level. Process exactly that many, adding their children for the next round. On “3 9 20 # # 15 7” the result is [3] [9, 20] [15, 7].

The size snapshot is the one trick of the whole group; every other problem here adds a small rule on top of the same loop.

Java
1static List<List<Integer>> levels(TreeNode root) {
2    List<List<Integer>> out = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                     // exactly the nodes of this level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        out.add(level);
15    }
16    return out;
17}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(w)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].
24.04.2

Zigzag traversal

**Zigzag** (spiral) order reads level 0 left to right, level 1 right to left, level 2 left to right, and so on. Run the normal level loop and reverse the list on every odd level, or add elements to a LinkedList at the front or the back depending on the direction.

On the perfect tree “1 2 3 4 5 6 7” the output is [1] [3, 2] [4, 5, 6, 7]. The tree itself is not changed; only the way each level is read changes.

Java
1static List<List<Integer>> zigzag(TreeNode root) {
2    List<List<Integer>> out = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    boolean leftToRight = true;
6    while (!queue.isEmpty()) {
7        int size = queue.size();
8        LinkedList<Integer> level = new LinkedList<>();
9        for (int i = 0; i < size; i++) {
10            TreeNode n = queue.poll();
11            if (leftToRight) level.addLast(n.val); else level.addFirst(n.val);
12            if (n.left != null) queue.add(n.left);
13            if (n.right != null) queue.add(n.right);
14        }
15        out.add(level);
16        leftToRight = !leftToRight;
17    }
18    return out;
19}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(w)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].
24.04.3

Left view

The **left view** is the first node of every level: what you see standing on the left. In the level loop, take the node at i == 0. On “1 2 3 # 5 # 4” it is [1, 2, 5]: the node 3 is hidden behind 2 on level 1, and on level 2 the node 5 (the right child of 2) is leftmost because 3 has no left child.

A deeper node can appear in the left view even when it is a right child. The view depends on level position, not on following left pointers.

Java
1static List<Integer> leftView(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        int size = queue.size();
7        for (int i = 0; i < size; i++) {
8            TreeNode n = queue.poll();
9            if (i == 0) out.add(n.val);              // first node of the level
10            if (n.left != null) queue.add(n.left);
11            if (n.right != null) queue.add(n.right);
12        }
13    }
14    return out;
15}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(w)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].
24.04.4

Right view

The **right view** is the last node of every level: take the node at i == size - 1. For “1 2 3 # 5 # 4” it is [1, 3, 4]. A depth-first alternative visits the right child first and records the first node seen at each new depth; it needs only O(h) space.

Java
1static List<Integer> rightView(TreeNode root) {
2    List<Integer> out = new ArrayList<>();
3    view(root, 0, out);
4    return out;
5}
6static void view(TreeNode n, int depth, List<Integer> out) {
7    if (n == null) return;
8    if (depth == out.size()) out.add(n.val);         // the first node reached on this level, going right-first
9    view(n.right, depth + 1, out);
10    view(n.left, depth + 1, out);
11}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].
24.04.5

Top/bottom views

For the **top** and **bottom** views the question is about columns, not levels. Give the root column 0; a left child is one column to the left (column - 1) and a right child one column to the right (column + 1). The top view is the first node reached in each column going down, and the bottom view is the last.

A breadth-first pass visits nodes level by level, so the first node seen in a column is the topmost, and each later node in the same column is lower. For “1 2 3 4 5 6 7” the top view is [4, 2, 1, 3, 7]. The bottom view is [4, 2, 6, 3, 7]: columns 0 holds 1, 5 and 6, and the last one reached, 6, is shown. (When two nodes share a row and a column, the one visited later in breadth-first order, here the right one, wins.)

Java
1// breadth-first with a column per node; first == true gives the top view, false the bottom view
2static List<Integer> columnView(TreeNode root, boolean first) {
3    TreeMap<Integer, Integer> byColumn = new TreeMap<>();
4    Deque<Object[]> queue = new ArrayDeque<>();
5    if (root != null) queue.add(new Object[]{root, 0});
6    while (!queue.isEmpty()) {
7        Object[] cur = queue.poll();
8        TreeNode n = (TreeNode) cur[0];
9        int col = (int) cur[1];
10        if (first) byColumn.putIfAbsent(col, n.val); else byColumn.put(col, n.val);
11        if (n.left != null) queue.add(new Object[]{n.left, col - 1});
12        if (n.right != null) queue.add(new Object[]{n.right, col + 1});
13    }
14    return new ArrayList<>(byColumn.values());
15}

Best

O(n log w)

Average

O(n log w)

Worst

O(n log n)

Space

O(n)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].
24.04.6

Vertical traversal

**Vertical order** lists every column from left to right, and within a column the nodes from top to bottom; nodes with the same row and column are ordered by value. Record (column, row, value) for every node, and sort by those keys.

On “3 9 20 # # 15 7” the output is [9] [3, 15] [20] [7]: 3 and 15 share column 0. On “1 2 3 4 6 5 7” the nodes 1, 5 and 6 land in column 0, and 5 and 6 share both row and column, so they appear as [1, 5, 6]: value order breaks the tie, although 6 was reached first.

Java
1static List<List<Integer>> verticalOrder(TreeNode root) {
2    TreeMap<Integer, List<int[]>> byColumn = new TreeMap<>();      // column -> {row, value}
3    Deque<Object[]> queue = new ArrayDeque<>();
4    if (root != null) queue.add(new Object[]{root, 0, 0});
5    while (!queue.isEmpty()) {
6        Object[] cur = queue.poll();
7        TreeNode n = (TreeNode) cur[0];
8        int col = (int) cur[1], row = (int) cur[2];
9        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
10        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
11        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
12    }
13    List<List<Integer>> out = new ArrayList<>();
14    for (List<int[]> list : byColumn.values()) {
15        list.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
16        List<Integer> column = new ArrayList<>();
17        for (int[] e : list) column.add(e[1]);
18        out.add(column);
19    }
20    return out;
21}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Level order, zigzag, side views, top and bottom views, vertical order

Interactive · edit the input

Your input

Try

binary tree · 7 nodes

1
2
4
5
3
6
7
Current nodeWaiting in the queueAlready processedPart of the answer

queue (front first)

1
Setup

Level order: a breadth-first pass visits the tree level by level.

Step 1 / 9
Java
1static List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> levels = new ArrayList<>();
3    Deque<TreeNode> queue = new ArrayDeque<>();
4    if (root != null) queue.add(root);
5    while (!queue.isEmpty()) {
6        int size = queue.size();                 // exactly the nodes of one level
7        List<Integer> level = new ArrayList<>();
8        for (int i = 0; i < size; i++) {
9            TreeNode n = queue.poll();
10            level.add(n.val);
11            if (n.left != null) queue.add(n.left);
12            if (n.right != null) queue.add(n.right);
13        }
14        levels.add(level);   // zigzag: reverse every odd level; left view: level.get(0); right view: last element
15    }
16    return levels;
17}
18// top, bottom and vertical views: carry a column with each queued node (left child: column - 1, right child: column + 1)
19static void columns(TreeNode root, TreeMap<Integer, List<int[]>> byColumn) {   // {row, value} per column
20    Deque<Object[]> queue = new ArrayDeque<>();
21    queue.add(new Object[]{root, 0, 0});
22    while (!queue.isEmpty()) {
23        Object[] cur = queue.poll();
24        TreeNode n = (TreeNode) cur[0]; int col = (int) cur[1], row = (int) cur[2];
25        byColumn.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, n.val});
26        if (n.left != null) queue.add(new Object[]{n.left, col - 1, row + 1});
27        if (n.right != null) queue.add(new Object[]{n.right, col + 1, row + 1});
28    }
29}

Live state

result

Level order

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L1result=Level orderLevel order: a breadth-first pass visits the tree level by level.
2L10result=Level order level=0Visit 1 on level 0.
3L10result=Level order level=1Visit 2 on level 1.
4L10result=Level order level=1Visit 3 on level 1.
5L10result=Level order level=2Visit 4 on level 2.
6L10result=Level order level=2Visit 5 on level 2.
7L10result=Level order level=2Visit 6 on level 2.
8L10result=Level order level=2Visit 7 on level 2.
9L16result=Level orderLevel order: [1] [2, 3] [4, 5, 6, 7].

Practice ladder

Now try it yourself

Easy

  • Average of Levels in Binary Tree
  • Minimum Depth of Binary Tree

Medium

  • Binary Tree Level Order Traversal
  • Binary Tree Zigzag Level Order Traversal
  • Binary Tree Right Side View
  • Binary Tree Vertical Order Traversal

Advanced

  • Vertical Order Traversal of a Binary Tree
  • Maximum Width of Binary Tree

Key takeaways

  • Snapshot the queue size at the start of each round to separate levels.
  • Zigzag only changes how each level is read; left and right views take the first or last node of a level.
  • Top, bottom and vertical views assign column numbers: left child -1, right child +1.
  • Ties in vertical order are broken by row first, then by value.