LESSON 328 OF 415 · BINARY TREES

Zigzag Tree Traversal in Swift: DFS by Level, Then Reverse Odd Levels

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, nil, nil, 15, 7]
    3
   / \
  9  20
    /  \
   15   7

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

STEP 1 OF 9

Guided

Ctrl + Enter to check

SWIFT · BINARY TREES

Zigzag Tree Traversal in Swift, explained

Problem overview

The method zigzagTraversal receives the root of a binary tree as a TreeNode? and returns its values level by level, as an array of arrays. The levels alternate in direction: level 0 (the root) is read from left to right, level 1 from right to left, level 2 from left to right again, and so on.

For the tree with root 3, children 9 and 20, and 20's children 15 and 7, the levels read left to right are [3], [9, 20] and [15, 7]. Level 1 is odd, so it is flipped. The answer is [[3], [20, 9], [15, 7]].

Approach: collect by level, then flip the odd ones

The usual way to get a tree level by level is a queue. This lesson takes another route with a depth-first search. Every call knows its depth, so it can put the node's value into the array for that depth. If the search always visits the left child before the right child, then each level's array fills from left to right, because within one level the nodes are met in left-to-right order.

Once the search finishes, every level is in left-to-right order. The zigzag only changes the direction of the odd levels, so a short loop reverses the arrays at positions 1, 3, 5 and so on.

Splitting the work into two phases keeps each part simple. The search doesn't need to know about directions, and the flipping loop doesn't need to know about the tree.

On the example, the search visits 3 (level 0), then 9 (level 1), whose children are missing, then 20 (level 1), then 15 and 7 (level 2). The levels are [[3], [9, 20], [15, 7]]. Reversing the array at position 1 gives [[3], [20, 9], [15, 7]].

Step by step

Plan the main method. Declare result as an empty [[Int]] with var and call the helper dfs with the root, level 0 and &result. The root sits on level 0.
Flip the odd levels. Loop over stride(from: 1, to: result.count, by: 2), which gives 1, 3, 5 and so on up to but not including result.count, and reverse result[level] in place with reverse().
Return result.
Declare the helper dfs with the unlabeled parameters _ root: TreeNode?, _ level: Int and _ result: inout [[Int]]. The parameter is inout because the helper adds to the caller's array.
Handle a missing node: if root == nil, return. Calls on missing children stop here.
Make sure the level has an array. If level >= result.count, append an empty [Int](). The search goes down one level at a time, so the level is never more than one past the last array.
Store the value with result[level].append(root!.val). The nil check makes the force-unwrap safe.
Recurse into the left child with level + 1.
Recurse into the right child the same way. Left before right is what keeps each level in left-to-right order.

The solution in Swift

class Solution {
    func dfs(_ root: TreeNode?, _ level: Int, _ result: inout [[Int]]) {
        if root == nil {
            return
        }
        if level >= result.count {
            result.append([Int]())
        }
        result[level].append(root!.val)
        dfs(root!.left, level + 1, &result)
        dfs(root!.right, level + 1, &result)
    }
    func zigzagTraversal(_ root: TreeNode?) -> [[Int]] {
        var result = [[Int]]()
        dfs(root, 0, &result)
        for level in stride(from: 1, to: result.count, by: 2) {
            result[level].reverse()
        }
        return result
    }
}

Swift details worth a closer look:

Nested arrays. [[Int]] is an array whose elements are arrays of Int. result[level].append(...) changes the inner array stored at that position, in place. Because arrays are value types, this does not affect any other variable.
inout and &. A normal array parameter is a constant copy. The inout parameter and the &result argument make every recursive call work on the caller's array.
reverse() versus reversed(). reverse() changes the array in place and returns nothing, which is why it is called on result[level]. reversed() leaves the array alone and returns a reversed view that you would have to assign back.
stride(from:to:by:). The end value is excluded, so with a count of 1 (just the root) the loop runs zero times, and with a count of 3 it runs once, for level 1. Using through: instead would go up to result.count itself when it fits the step, and then result[level] would crash.
The empty-tree case. A nil root makes dfs return at once, so result stays empty and the stride is empty too.

Complexity

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

Time: O(n). The search handles each node once and does constant work per node (amortized for append). Reversing the odd levels touches each of their values once more, so the whole loop also stays within O(n).

Space: O(n). The output holds all n values. The recursion adds O(h) for the call stack, and h is at most n.

Edge cases and common mistakes

An empty tree. The method returns [].
A single node. The result is [[1]]. Level 0 is never reversed.
Reversing the wrong levels. The first level to flip is 1, not 0. Starting the stride at 0 would flip the root's level and every even level.
Visiting right before left. Each level would be collected right to left, and the odd levels would come out in the wrong direction after the flip.
Forgetting to create the level's array. Writing to result[level] before it exists is an index-out-of-range error and crashes the program.
Missing children. Gaps don't leave placeholders. A level contains only the nodes that exist, in order.

Testing

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

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

Start learning free