Make delicious recipes!

Print tree in spiral order

Use two stacks instead of one queue in level order traversal.

void traverseSpiral (TreeNode root)
    Stack st1, st2;

    st1.push (root);

    while (st1.size() > 0 || st2.size() > 0)
        while (st1.size() > 0)
            TreeNode n = st1.pop();
            if (n.right != null) st2.push (n.right);
            if (n.left != null) st2.push (n.left);
        while (st2.size() > 0)
            TreeNode n = st2.pop();
            // IMP: order of insertion should be different in 2 stacks
            if (n.left != null) st1.push (n.left);
            if (n.right != null) st1.push (n.right);

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal