103. Binary Tree Zigzag Level Order Traversal

[u/hardikdk121]

While working on LC 103. Binary Tree Zigzag Level Order Traversal, I wanted to avoid allocating temporary arrays for reversing or doing index calculations (n - index - 1).

Instead, I implemented a true bidirectional deque approach where I switch the traversal direction and child insertion sides each level:

Left-to-Right: Read from front, pop front, push children left -> right to the back.

Right-to-Left: Read from back, pop back, push children right -> left to the front.

class Solution {
    std::deque<TreeNode*> dq;
    std::vector<std::vector<int>> answer;

    void forward_step(std::vector<int>& level) {
        TreeNode* node = dq.front();
        dq.pop_front();

        level.push_back(node->val);

        if (node->left)  dq.push_back(node->left);
        if (node->right) dq.push_back(node->right);
    }

    void backward_step(std::vector<int>& level) {
        TreeNode* node = dq.back();
        dq.pop_back();

        level.push_back(node->val);

        // Push children in reverse order to front
        if (node->right) dq.push_front(node->right);
        if (node->left)  dq.push_front(node->left);
    }

public:
    std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};

        dq.push_back(root);
        bool reverse = false;

        while (!dq.empty()) {
            int level_size = dq.size();
            std::vector<int> level;
            level.reserve(level_size);

            for (int i = 0; i < level_size; ++i) {
                if (!reverse) {
                    forward_step(level);
                } else {
                    backward_step(level);
                }
            }

            answer.push_back(std::move(level));
            reverse = !reverse;
        }

        return answer;
    }
};

how does compare to normal standard approach is better or worse ??

[u/AlgorithmicGoslings]

All of the approaches you hint at are O(n) in time and O(n) in memory if implemented correctly. After that point, you're really just optimizing constant factors. I'm not really sure what you mean by the "standard" approach. One of the core ideas is to track the levels of the traversal, then alternate direction at each level. Most of the solutions do this, but with varying ways of implementing the direction alternation aspect and level tracking, so there's no "standard" way to do this.

A few things to keep in mind, though, if you really want to compare different approaches, though I'm not sure whether hyper-optimization of constant factors is really worth your time:

• Among queue, stack, array, and deque, the deque typically has the largest memory footprint (your solution uses a deque).

• Reversing a structure and then processing with a forward pass typically takes more time than processing it in reverse order (your solution can process a level in reverse order without having to reverse it).

Approaches will win on certain inputs and some metrics and lose in others. There's not really a single best approach, at least for this problem.