Start learning free

LESSON 308 OF 347 · BINARY TREES

Zigzag Tree Traversal in C#: Level by Level with Two Stacks

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

    C# · BINARY TREES

    Zigzag Tree Traversal in C#, explained

    Problem overview

    The method zigzagTraversal receives the root of a binary tree and returns a List<List<int>> with one inner list per level. The root's level is read from left to right, the next level from right to left, and the direction keeps alternating.

    For [3, 9, 20, null, null, 15, 7] the answer is [[3], [20, 9], [15, 7]]: the root alone, then 9 and 20 reversed, then 15 and 7 in their normal order.

    Approach: let the stacks do the reversing

    The other lesson on this problem walks the tree depth first and reverses every odd level afterwards. This lesson produces each level already in the right order, using the fact that a stack hands items back in the reverse of the order they were pushed.

    It uses two stacks:

    • currentLevelStack holds the nodes of the level being read. Nodes are popped from it one by one, and each popped value goes into the result in that order.
    • nextLevelStack collects the children of those nodes. They form the next level.

    The trick is the order in which children are pushed. On an even level, the nodes are read left to right, and the next level must be read right to left. A stack pops the last item pushed first, so the left child is pushed first and the right child second, which makes the right one come out first. On an odd level it is the opposite: the right child is pushed first, so that the left child is on top and the next level is read left to right.

    When the current stack becomes empty, the level is finished. The next stack holds the whole next level and takes the place of the current one, and a fresh empty stack takes the place of the next one.

    Step by step

    1. Create the result as an empty List<List<int>>.
    2. Create the two stacks, currentLevelStack and nextLevelStack, both empty Stack<TreeNode> objects.
    3. Push the root through the helper AddToStack, using a one-element TreeNode[]. The helper skips null, so an empty tree leaves the stack empty, the loop never runs and the result stays empty.
    4. Start the level counter level at 0.
    5. Loop while currentLevelStack.Count is above 0.
    6. Pop a node from currentLevelStack.
    7. Record its value with the helper AddToResult(result, level, node.val), which creates the level's list if it doesn't exist yet.
    8. On an even level, push the children into nextLevelStack as left then right. Missing children are passed to the helper as well, and it leaves them out.
    9. On an odd level, push them as right then left.
    10. Switch levels when the current stack is empty. Assign nextLevelStack to currentLevelStack, give nextLevelStack a new empty stack, and increase level.
    11. Return result after the loop.
    12. Write AddToResult. If level >= result.Count, add a new empty list. Then add the value to result[level]. Levels are visited in order, so the new level is always the next index.
    13. Write AddToStack. It loops over a TreeNode[] and pushes each node that isn't null.

    The solution in C#

    class Solution {

    public void AddToStack(Stack<TreeNode> stack, TreeNode[] nodes) {
        foreach (TreeNode node in nodes) {
            if (node != null) {
                stack.Push(node);
            }
        }
    }

    public void AddToResult(List<List<int>> result, int level, int value) {
        if (level >= result.Count) {
            result.Add(new List<int>());
        }
        result[level].Add(value);
    }

    public List<List<int>> zigzagTraversal(TreeNode root) {
        List<List<int>> result = new List<List<int>>();
        Stack<TreeNode> currentLevelStack = new Stack<TreeNode>();
        Stack<TreeNode> nextLevelStack = new Stack<TreeNode>();

        AddToStack(currentLevelStack, new TreeNode[]{root});
        int level = 0;

        while (currentLevelStack.Count > 0) {
            TreeNode node = currentLevelStack.Pop();

            AddToResult(result, level, node.val);

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

            if (currentLevelStack.Count == 0) {
                currentLevelStack = nextLevelStack;
                nextLevelStack = new Stack<TreeNode>();
                ++level;
            }
        }

        return result;
    }
};

    The C# points to notice:

    • Stacks come from System.Collections.Generic. Push adds to the top, Pop removes and returns the top, and Count is the size. Popping an empty stack throws an InvalidOperationException, which the loop condition prevents.
    • Array initializers. new TreeNode[]{node.left, node.right} builds an array holding the two children in that order. Arrays can contain null for reference types, which is how missing children get passed along.
    • Reassigning locals. currentLevelStack = nextLevelStack; copies the reference, so both names point to the same stack for a moment. The next statement gives nextLevelStack a new object, so they separate again.
    • ++level increments the variable. Used as a statement, it behaves the same as level++.
    • The method name. The lesson's public method is zigzagTraversal, with a lowercase first letter, and it must keep that spelling.

    Complexity

    Time: O(n). Every node is pushed once, popped once and added to the result once, and each of those operations takes constant time.

    Space: O(w) for the stacks plus the output, where w is the width of the tree, the size of its largest level. The two stacks never hold more than about two levels together. The result holds all n values.

    Edge cases and common mistakes

    • Empty tree. AddToStack drops the null root, the loop doesn't start, and the result is empty. Pushing null directly would crash at node.val.
    • Switching levels too early. The swap must happen only when currentLevelStack is empty. Swapping after each node would mix the levels.
    • Wrong push order. Pushing left then right on every level would produce a plain right-to-left order on every level, not an alternating one. The order depends on the parity of level.
    • Reusing the old stack object. After the swap, nextLevelStack must be a different stack from currentLevelStack. Without the assignment of a new one, the children would be pushed back onto the stack being read.
    • Missing children. Nodes with only one child are fine, because the helper skips the empty side.
    • Assuming levels are full. A level contains only the nodes that exist, so inner lists can have different lengths.

    Testing

    • [3, 9, 20, null, null, 15, 7] gives [[3], [20, 9], [15, 7]].
    • A single node [1] gives [[1]].
    • An empty tree gives [].
    • The tree [1, 2, 3, 4, 5, 6, 7] gives [[1], [3, 2], [4, 5, 6, 7]].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free