Ronzii's Blog

Just your average geek's blog

Spiral Order Traversal in a Tree

void iterativeSpiralTraversal(TreeNode* root)
{
    stack<TreeNode*> currentLevel, nextLevel;
    currentLevel.push(root);
    bool direction = 1;
    while(!currentLevel.empty())
    {
        TreeNode* current = currentLevel.top();
        currentLevel.pop();
        if(current)
        {
            cout<<current->value<<" ";
            if(direction)
            {
                if(current->left)
                    nextLevel.push(current->left);
                if(current->right)
                    nextLevel.push(current->right);
            }
            else
            {
                if(current->right)
                    nextLevel.push(current->right);
                if(current->left)
                    nextLevel.push(current->left);
            }
        }
        if(currentLevel.empty())
        {
            cout<<endl;
            swap(currentLevel,nextLevel);
            direction = !direction;
        }
    }
}

April 1, 2012 Posted by | C++, Data Structures | , , , , | 1 Comment