Given a binary tree, write a method that traverses the tree in zigzag order (similar to level-order traversal but toggle left to right and right to left visiting of the nodes at each level).

void ZigzagOrderTraversal(Node *n)
{
    if (!n)
        return;
 
    bool toggle = true;
    stack<Node*> lr; // Left to right
    stack<Node*> rl; // Right to left
    lr.push(n);
 
    while (!lr.empty() || !rl.empty())
    {
        if (toggle)
        {
            while (!lr.empty())
            {
                n = lr.top();
                lr.pop();
 
                cout << n->value << " "; // Visit
 
                if (n->left)
                    rl.push(n->left);
                if (n->right)
                    rl.push(n->right);
            }
 
            toggle = toggle ^ true;
        }
        else
        {
            while (!rl.empty())
            {
                n = rl.top();
                rl.pop();
 
                cout << n->value << " "; // Visit
 
                if (n->right)
                    lr.push(n->right);
                if (n->left)
                    lr.push(n->left);
            }
 
            toggle = toggle ^ true;
        }
    }
}