Spiral or Zigzag Traversal in a Binary Tree

The following visuals will give you an idea about how the spiral or zigzag order traversal looks like. This traversal is based on Level order traversal. We need to keep track of the nodes in each level to display accordingly.

As we can see above, tracking each level is very important during this traversal.

Approach 1: Using two stacks.

One of the commonly used approach is using 2 stacks.
The idea behind using 2 stacks is to clearly distinguish the nodes that are in same level.

• Initialize 2 stacks stack1 and stack2.
• Push root node in stack1.
• Pop the root and push the children of the root node in stack2.
• Pop the nodes in stack2 one by one, while inserting their children in the other stack.
• Continue until both the stacks are empty.

Note:
– From the above visualization, at each level, the direction of the traversal changes.
– When the direction of traversal is from right to left, push left node first and then the right node in the stack.
– When the direction of traversal is from left to right, push right node first and then the left node in the stack.
– Since stack is LIFO, hence the logic.

def spiralOrderIterative(root, start_dir):
    """
    :param root:
    :return:
    """
    if not root:
        return
    stack1, stack2 = [], []
    stack1.append(root)
    result = []
    while stack1 or stack2:
        while stack1:
            node = stack1.pop()
            result.append(node.data)
            if start_dir == 'right':
                push_rtl(stack2, node.left, node.right)
            else:
                push_ltr(stack2, node.left, node.right)
        while stack2:
            node = stack2.pop()
            result.append(node.data)
            if start_dir == 'left':
                push_rtl(stack1, node.left, node.right)
            else:
                push_ltr(stack1, node.left, node.right)
    return result
def push_rtl(stack, left, right):
    if left:
        stack.append(left)
    if right:
        stack.append(right)
def push_ltr(stack, left, right):
    if right:
        stack.append(right)
    if left:
        stack.append(left)
class TreeNode(object):
    def __init__(self, value):
        self.left = None
        self.right = None
        self.data = value
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.left = TreeNode('F')
root.right.right = TreeNode('G')
print spiralOrderIterative(root, 'left')
# Output:
#Starting RightOutput:   A, C, B, D, E, F, G
#Starting LeftOutput:   A, B, C, G, F, E, D

Coming up next: Recursive and Queue solution