LESSON 303 OF 348 · BINARY TREES

Zigzag Tree Traversal in Kotlin: DFS by Level, Then Reverse

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Example:

Input: root = [3, 9, 20, null, null, 15, 7]
    3
   / \
  9  20
    /  \
   15   7

Output: 
[
  [3],
  [20,9],
  [15,7]
]

STEP 1 OF 9

Guided

Ctrl + Enter to check

KOTLIN · BINARY TREES

Zigzag Tree Traversal in Kotlin, explained

Problem overview

The function zigzagTraversal receives the root of a binary tree, a TreeNode?, and returns a List<List<Int>>: one inner list per level of the tree, from the top down. The first level, the root, is read from left to right, the next level from right to left, and the direction keeps alternating.

For this tree:

level 0 is [3], level 1 read right to left is [20, 9], and level 2 read left to right is [15, 7]. The answer is [[3], [20, 9], [15, 7]].

Approach: collect left to right, then flip every other level

Reading a tree level by level is usually done with a queue, but a depth-first search can do it too, as long as each call knows which level its node is on. The root is on level 0, and a node's children are on the level below it.

The plan has two phases:

Walk the tree depth-first, visiting the left child before the right one. Each node is appended to the list of its level. Because the left child is always visited first, every level's list ends up in left-to-right order, even though the levels are filled in an interleaved way.
Reverse the lists of the odd levels (1, 3, 5, and so on). Level 0 and the other even levels stay as they are.

For the example, the walk visits 3, then 9, then 20, then 15, then 7. The level lists become [3], [9, 20] and [15, 7]. Flipping level 1 gives [20, 9]. Compared with building each level in the right direction from the start, this is easier to get right: the search is the ordinary left-then-right one, and the zigzag is a separate, small loop.

Step by step

Create result as an empty mutable list of mutable lists of Int, and call the helper dfs with the root, level 0 and result. The helper is written afterwards.
Flip the odd levels. Loop with level over 1 until result.size step 2, which gives 1, 3, 5 and so on, and reverse each of those lists in place.
Return result after the loop.
Declare the helper with the parameters root: TreeNode?, level: Int and result. The root is nullable because missing children are passed in too.
Return for a missing node. This is the base case that ends the recursion.
Make sure the level has a list. If level >= result.size, add a new empty list. A depth-first walk reaches a new level only one step deeper than the deepest one seen so far, so adding one list is always enough.
Store the value in the list for this level.
Recurse into the left child with level + 1.
Recurse into the right child the same way. The order, left before right, is what keeps each level left to right.

The solution in Kotlin

class Solution {
    fun dfs(root: TreeNode?, level: Int, result: MutableList<MutableList<Int>>) {
        if (root == null) {
            return
        }
        if (level >= result.size) {
            result.add(mutableListOf())
        }
        result[level].add(root.value)
        dfs(root.left, level + 1, result)
        dfs(root.right, level + 1, result)
    }

    fun zigzagTraversal(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        dfs(root, 0, result)
        for (level in 1 until result.size step 2) {
            result[level].reverse()
        }
        return result
    }
}

The Kotlin details worth knowing:

Ranges with step. 1 until result.size counts from 1 up to, but not including, result.size. Adding step 2 keeps every second value. With one level or none, the range is empty and the loop body never runs.
reverse() versus reversed(). reverse() on a MutableList changes the list in place and returns nothing. reversed() would return a new reversed list and leave the original alone. Writing result[level].reversed() in the loop would compute a list and throw it away, leaving the odd levels in the wrong order.
Nested mutable types. MutableList<MutableList<Int>> means the outer list can grow and each inner list can change. The helper needs both, so the helper's parameter is declared that way.
Type inference for mutableListOf(). In result.add(mutableListOf()) the compiler infers Int from the type of result, so no type argument is needed. The first declaration of result does need one, because nothing else tells the compiler what the list holds.
Returning a more specific type. The function returns List<List<Int>> but the value is a MutableList<MutableList<Int>>. That compiles, because List is read-only and covariant, so a list of mutable lists counts as a list of lists.
Smart cast. After if (root == null) return, root is treated as non-null, so root.value and root.left need no ?..

Complexity

Let n be the number of nodes and h the height of the tree.

Time: O(n). The search makes one call per node and one per missing child, with constant work in each. The reversing loop touches each value of the odd levels once more, which is at most n extra steps in total.

Space: O(n). The result holds all n values. On top of that, the recursion uses O(h) stack space, which is O(n) in the worst case of a chain-shaped tree.

Edge cases and common mistakes

Empty tree. A null root adds no lists, the loop range is empty, and the result is an empty list.
Single node. The result is [[1]]. There is no odd level to flip.
Visiting the right child first. Every level's list would be right to left, and flipping the odd levels would give the wrong direction on all of them.
Starting the loop at 0 or stepping by 1. Level 0 must stay as it is, and the even levels too. The loop starts at 1 and moves by 2.
Using reversed() instead of reverse(). It builds a new list without changing the stored one, so nothing is flipped.
Missing children. A node with a single child needs no special case. The call for the absent child returns at the first check and adds nothing, so no level gets an empty list.

Testing

The tree [3, 9, 20, null, null, 15, 7] in level order gives [[3], [20, 9], [15, 7]].
The tree [1, 2, 3, 4, 5, 6, 7] gives [[1], [3, 2], [4, 5, 6, 7]].
A single node [1] gives [[1]].
An empty tree gives [].

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free