Binary Tree Zigzag Level Order Traversal

Problem

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

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

Example 1:

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

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -100 <= Node.val <= 100

Pattern

Tree, Breadth-First Search, Binary Tree

Solution

The solution is the same as level order traversal, but reverse the order of the values if the depth is odd, starting at 0. The reason we reverse the order of the values instead of the order of the nodes is because then nodes added to the next level will also be reversed.

Code

from typing import List


class TreeNode:
    """Node in a binary tree.
    """

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def zigzagLevelOrder(root: TreeNode | None) -> List[List[int]]:
    """Traverse a binary tree in level order but zigzaging from left to right
    and right to left.
    """
    traversal = []
    level = [root] if root is not None else []
    depth = 0
    while len(level) > 0:
        values = []
        next_level = []
        for node in level:
            values.append(node.val)
            if node.left is not None:
                next_level.append(node.left)
            if node.right is not None:
                next_level.append(node.right)

        if depth % 2 == 1:
            values = values[::-1]
        traversal.append(values)
        level = next_level
        depth += 1

    return traversal

Test

>>> from binary_tree_zigzag_level_order_traversal__approach_1 import zigzagLevelOrder, TreeNode
>>> root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
>>> zigzagLevelOrder(root)
[[3], [20, 9], [15, 7]]
>>> zigzagLevelOrder(TreeNode(1))
[[1]]
>>> zigzagLevelOrder(None)
[]

Complexity

\(n\) is the number of nodes in the binary tree

Time: \(O(n)\) — visit each node once

Auxiliary Space: \(O(n)\) — next_level holds one level of nodes, up to

\(O(n / 2)\) for a full binary tree

class binary_tree_zigzag_level_order_traversal__approach_1.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

binary_tree_zigzag_level_order_traversal__approach_1.zigzagLevelOrder(root: TreeNode | None) → List[List[int]]

Traverse a binary tree in level order but zigzaging from left to right and right to left.