Start learning free

LESSON 309 OF 348 · BINARY TREES

Zigzag Tree Traversal in TypeScript: Two Stacks, Level by Level

Practice O(n) Read the full explanation

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 16
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

    Zigzag Tree Traversal in TypeScript, explained

    Problem overview

    The method zigzagTraversal receives the root of a binary tree (a TreeNode | null) and returns the values level by level as a number[][]. The first level is read left to right, the next one right to left, and the direction keeps alternating.

    For the tree built from [3, 9, 20, null, null, 15, 7], the root 3 has children 9 and 20, and 20 has children 15 and 7. The levels are [3], then [20, 9] and then [15, 7], so the result is [[3], [20, 9], [15, 7]].

    Approach: let the stacks do the reversing

    A stack gives items back in the opposite order from the one in which they went in. That is exactly the reversal the zigzag needs, so there is no need to reverse any list afterwards.

    Use two stacks. currentLevelStack holds the nodes of the level being read, and each pop gives the next node to record. nextLevelStack collects the children of the nodes just read. Which child is pushed first decides the direction the next level will be popped:

    • On an even level, the next level must come out right to left. Push the left child first and the right child second, so the right child is on top.
    • On an odd level, the next level must come out left to right. Push the right child first, so the left child is on top.

    When the current stack runs empty, the level is finished and the next stack holds the whole next level. The two swap roles and the level number goes up. Only two stacks are alive at any time.

    For the example, level 0 pops 3 and pushes 9, then 20. Level 1 pops 20 first, then 9; reading 20 (odd level) pushes its children right first, so 15 ends up on top. Level 2 therefore pops 15, then 7.

    Step by step

    1. Create the result, an empty number[][] with one inner array per level.
    2. Create the two stacks as TreeNode[] arrays, declared with let because they are reassigned when a level ends.
    3. Push the root through a helper, addToStack, that skips null values. For an empty tree nothing is pushed and the loop never runs.
    4. Track the level number, starting at 0 for the root.
    5. Loop while the current stack has nodes. A length of 0 counts as false.
    6. Pop a node. The loop condition guarantees one exists, so the non-null assertion ! is safe.
    7. Record its value with a helper, addToResult, that creates the level's list the first time the level is reached.
    8. Push the children in the order that suits the level: left then right on even levels.
    9. Push right then left on odd levels.
    10. When the current stack is empty, promote the next stack to current, give the next stack a fresh empty array and increase the level.
    11. Return the result after the loop.
    12. Write the helpers. addToResult pushes an empty array when level is at least result.length, then pushes the value. addToStack loops over a list of possibly-null nodes and pushes only the real ones.

    The solution in TypeScript

    class Solution {

    addToStack(stack: TreeNode[], nodes: (TreeNode | null)[]): void {
        for (const node of nodes) {
            if (node) {
                stack.push(node);
            }
        }
    }

    addToResult(result: number[][], level: number, value: number): void {
        if (level >= result.length) {
            result.push([]);
        }
        result[level].push(value);
    }

    zigzagTraversal(root: TreeNode | null): number[][] {
        const result: number[][] = [];
        let currentLevelStack: TreeNode[] = [];
        let nextLevelStack: TreeNode[] = [];

        this.addToStack(currentLevelStack, [root]);
        let level = 0;

        while (currentLevelStack.length) {
            const node = currentLevelStack.pop()!;

            this.addToResult(result, level, node.val);

            if (level % 2 === 0) {
                this.addToStack(nextLevelStack, [node.left, node.right]);
            } else {
                this.addToStack(nextLevelStack, [node.right, node.left]);
            }

            if (currentLevelStack.length === 0) {
                currentLevelStack = nextLevelStack;
                nextLevelStack = [];
                ++level;
            }
        }

        return result;
    }
}

    The TypeScript details worth a closer look:

    • The non-null assertion. pop() has the type TreeNode | undefined, because an array can be empty. The trailing ! tells the compiler that the value is not undefined. It is only a promise to the compiler: it adds no check and no code to the compiled JavaScript, so it's safe only because the loop condition guarantees a node.
    • Typing the helper's input. (TreeNode | null)[] is an array whose elements may be null. That lets the caller pass [node.left, node.right] without checking each child, while the stacks themselves stay typed TreeNode[].
    • Truthiness in conditions. while (currentLevelStack.length) works because the number 0 is falsy and any other number is truthy. if (node) filters out null.
    • let versus const. The stacks use let because the variables are reassigned at the end of a level. result and node use const.
    • Swapping by reassignment. nextLevelStack = [] creates a new array instead of clearing the old one. The old array is now currentLevelStack, so it must not be touched.

    Complexity

    Let n be the number of nodes.

    Time: O(n). Every node is pushed once, popped once and recorded once, and each of those steps is constant work. There is no sorting and no reversal.

    Space: O(n). The result holds all values. The two stacks together hold at most two adjacent levels, which is at most n nodes. A wide tree makes them large; a narrow one keeps them small.

    Edge cases and common mistakes

    • An empty tree. addToStack pushes nothing, the loop is skipped and the result is [].
    • Pushing the children in the wrong order. If you push left then right on every level, the third level of a full seven-node tree would come out as [5, 4, 7, 6], which is neither direction. The push order must alternate.
    • Reading the wrong direction. Remember that the order of pushing is the reverse of the order of reading. Pushing for level L + 1 happens while level L is being read.
    • Checking the stack before the pop. The end-of-level test must come after the pop and the pushes. At that moment an empty current stack means the last node of the level was just handled.
    • Forgetting to reset the next stack. If both variables kept pointing to the same array, nodes of different levels would mix.
    • Pushing null children. A null on the stack would crash the next pop's node.val. The filter in addToStack prevents it.

    Testing

    • [3, 9, 20, null, null, 15, 7] gives [[3], [20, 9], [15, 7]].
    • [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 TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free