{"id":367,"date":"2020-03-30T06:11:40","date_gmt":"2020-03-30T06:11:40","guid":{"rendered":"http:\/\/www.datastructure.org\/?p=367"},"modified":"2025-04-21T13:49:11","modified_gmt":"2025-04-21T13:49:11","slug":"spiral-or-zigzag-traversal-in-a-binary-tree","status":"publish","type":"post","link":"https:\/\/www.bhargaviurs.com\/index.php\/2020\/03\/30\/spiral-or-zigzag-traversal-in-a-binary-tree\/","title":{"rendered":"Spiral or Zigzag Traversal in a Binary Tree"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">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. <\/p>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/www.bhargaviurs.com\/wp-content\/uploads\/2020\/04\/spiral_traversal.gif\" alt=\"\" class=\"wp-image-403\" width=\"656\" height=\"369\"\/><figcaption> <strong>Starting Right<br> Output<\/strong>:&nbsp;&nbsp; A, C, B, D, E, F, G <\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/www.bhargaviurs.com\/wp-content\/uploads\/2020\/04\/spiral_traversal_left.gif\" alt=\"\" class=\"wp-image-392\" width=\"704\" height=\"396\"\/><figcaption><strong>Starting Left<br> Output<\/strong>:&nbsp;&nbsp; A, B, C, G, F, E, D <\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">As we can see above, tracking each level is very important during this traversal. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Approach 1:<\/strong> <strong>Using two stacks.<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">One of the commonly used approach is using 2 stacks. <br>The idea behind using 2 stacks is to clearly distinguish the nodes that are in same level. <\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Spiral Tree Traversal: 2 stacks\" width=\"1100\" height=\"619\" src=\"https:\/\/www.youtube.com\/embed\/a592MMuC9g0?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<ul class=\"wp-block-list\"><li>Initialize 2 stacks stack1 and stack2.<\/li><li>Push root node in stack1. <\/li><li>Pop the root and push the children of the root node in stack2.<\/li><li>Pop the nodes in stack2 one by one, while inserting their children in the other stack. <\/li><li>Continue until both the stacks are empty. <\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Note<\/strong>:<br>&#8211; From the above visualization,  at each level,  the direction of the traversal changes. <br>&#8211; When the direction of traversal is from right to left, push left node first and then the right node in the stack. <br>&#8211; When the direction of traversal is from left to right, push right node first and then the left node in the stack. <br>&#8211; Since stack is LIFO, hence the logic.<\/p>\n\n\n\n<pre title=\"Spiral traversal\" class=\"wp-block-code\"><code lang=\"python\" class=\"language-python\">def spiralOrderIterative(root, start_dir):\n    \"\"\"\n    :param root:\n    :return:\n    \"\"\"\n    if not root:\n        return\n    stack1, stack2 = [], []\n    stack1.append(root)\n    result = []\n    while stack1 or stack2:\n        while stack1:\n            node = stack1.pop()\n            result.append(node.data)\n            if start_dir == 'right':\n                push_rtl(stack2, node.left, node.right)\n            else:\n                push_ltr(stack2, node.left, node.right)\n        while stack2:\n            node = stack2.pop()\n            result.append(node.data)\n            if start_dir == 'left':\n                push_rtl(stack1, node.left, node.right)\n            else:\n                push_ltr(stack1, node.left, node.right)\n    return result\ndef push_rtl(stack, left, right):\n    if left:\n        stack.append(left)\n    if right:\n        stack.append(right)\ndef push_ltr(stack, left, right):\n    if right:\n        stack.append(right)\n    if left:\n        stack.append(left)\nclass TreeNode(object):\n    def __init__(self, value):\n        self.left = None\n        self.right = None\n        self.data = value\nroot = TreeNode('A')\nroot.left = TreeNode('B')\nroot.right = TreeNode('C')\nroot.left.left = TreeNode('D')\nroot.left.right = TreeNode('E')\nroot.right.left = TreeNode('F')\nroot.right.right = TreeNode('G')\nprint spiralOrderIterative(root, 'left')\n# Output:\n#Starting Right\u000bOutput:   A, C, B, D, E, F, G\n#Starting Left\u000bOutput:   A, B, C, G, F, E, D<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Coming up next: Recursive and Queue solution<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-367","post","type-post","status-publish","format-standard","hentry","category-linked-list","entry"],"_links":{"self":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/367","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/comments?post=367"}],"version-history":[{"count":2,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/367\/revisions"}],"predecessor-version":[{"id":442,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/posts\/367\/revisions\/442"}],"wp:attachment":[{"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/media?parent=367"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/categories?post=367"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bhargaviurs.com\/index.php\/wp-json\/wp\/v2\/tags?post=367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}