Level Order in spiral form

Time: O(n)

Space: O(n)

Intuition

Alternate direction each level. Use two stacks: one for left-to-right levels, one for right-to-left. Or BFS with a direction flag.

Algorithm

1Use two stacks s1 (current) and s2 (next).
2Left-to-right level: push right then left child to s2.
3Right-to-left level: push left then right child to s2.
4Swap stacks after each level.

Common Pitfalls

•When printing left-to-right, push children right-then-left to next stack (stack reverses order).

Level Order in spiral form.java

Java

// Approach: BFS with a flag to reverse alternate levels.
// Use two stacks or deque to alternate direction.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> findSpiral(Node root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
            return res;

        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        boolean leftToRight = false;

        while (!q.isEmpty()) {
            int size = q.size();
            ArrayList<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                levelList.add(node.data);

                if (node.left != null)
                    q.offer(node.left);
                if (node.right != null)
                    q.offer(node.right);
            }

            if (leftToRight)
                res.addAll(levelList);
            else {
                for (int i = levelList.size() - 1; i >= 0; i--)
                    res.add(levelList.get(i));
            }

            leftToRight = !leftToRight;
        }

        return res;
    }
}

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

Was this solution helpful?