{"id":27629,"date":"2018-04-09T20:08:07","date_gmt":"2018-04-09T14:38:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27629"},"modified":"2018-09-16T13:37:24","modified_gmt":"2018-09-16T08:07:24","slug":"python-program-inorder-tree-traversal-without-recursion","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-inorder-tree-traversal-without-recursion\/","title":{"rendered":"Python Program &#8211; Inorder Tree Traversal without Recursion"},"content":{"rendered":"<p>Using <a href=\"http:\/\/en.wikipedia.org\/wiki\/Stack_%28data_structure%29\">Stack <\/a>is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See <a href=\"http:\/\/neural.cs.nthu.edu.tw\/jang\/courses\/cs2351\/slide\/animation\/Iterative%20Inorder%20Traversal.pps\">this <\/a>for step wise step execution of the algorithm.<\/p>\n<pre>1) Create an empty stack S.\r\n2) Initialize current node as root\r\n3) Push the current node to S and set current = current->left until current is NULL\r\n4) If current is NULL and stack is not empty then \r\n     a) Pop the top item from stack.\r\n     b) Print the popped item, set current = popped_item->right \r\n     c) Go to step 3.\r\n5) If current is NULL and stack is empty then we are done.\r\n<\/pre>\n<p>Let us consider the below tree for example<\/p>\n<pre>            1\r\n          \/   \\\r\n        2      3\r\n      \/  \\\r\n    4     5\r\n\r\nStep 1 Creates an empty stack: S = NULL\r\n\r\nStep 2 sets current as address of root: current -> 1\r\n\r\nStep 3 Pushes the current node and set current = current->left until current is NULL\r\n     current -> 1\r\n     push 1: Stack S -> 1\r\n     current -> 2\r\n     push 2: Stack S -> 2, 1\r\n     current -> 4\r\n     push 4: Stack S -> 4, 2, 1\r\n     current = NULL\r\n\r\nStep 4 pops from S\r\n     a) Pop 4: Stack S -> 2, 1\r\n     b) print \"4\"\r\n     c) current = NULL \/*right of 4 *\/ and go to step 3\r\nSince current is NULL step 3 doesn't do anything. \r\n\r\nStep 4 pops again.\r\n     a) Pop 2: Stack S -> 1\r\n     b) print \"2\"\r\n     c) current -> 5\/*right of 2 *\/ and go to step 3\r\n\r\nStep 3 pushes 5 to stack and makes current NULL\r\n     Stack S -> 5, 1\r\n     current = NULL\r\n\r\nStep 4 pops from S\r\n     a) Pop 5: Stack S -> 1\r\n     b) print \"5\"\r\n     c) current = NULL \/*right of 5 *\/ and go to step 3\r\nSince current is NULL step 3 doesn't do anything\r\n\r\nStep 4 pops again.\r\n     a) Pop 1: Stack S -> NULL\r\n     b) print \"1\"\r\n     c) current -> 3 \/*right of 5 *\/  \r\n\r\nStep 3 pushes 3 to stack and makes current NULL\r\n     Stack S -> 3\r\n     current = NULL\r\n\r\nStep 4 pops from S\r\n     a) Pop 3: Stack S -> NULL\r\n     b) print \"3\"\r\n     c) current = NULL \/*right of 3 *\/<\/pre>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20do%20inorder%20traversal%20without%20recursion%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20Iterative%20function%20for%20inorder%20tree%20traversal%0Adef%20inOrder(root)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Set%20current%20to%20root%20of%20binary%20tree%0A%20%20%20%20current%20%3D%20root%20%0A%20%20%20%20s%20%3D%20%5B%5D%20%23%20initialze%20stack%0A%20%20%20%20done%20%3D%200%0A%20%20%20%20%20%0A%20%20%20%20while(not%20done)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Reach%20the%20left%20most%20Node%20of%20the%20current%20Node%0A%20%20%20%20%20%20%20%20if%20current%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Place%20pointer%20to%20a%20tree%20node%20on%20the%20stack%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20before%20traversing%20the%20node\u2019s%20left%20subtree%0A%20%20%20%20%20%20%20%20%20%20%20%20s.append(current)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.left%20%0A%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20BackTrack%20from%20the%20empty%20subtree%20and%20visit%20the%20Node%0A%20%20%20%20%20%20%20%20%23%20at%20the%20top%20of%20the%20stack%3B%20however%2C%20if%20the%20stack%20is%20%0A%20%20%20%20%20%20%20%20%23%20empty%20you%20are%20done%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if(len(s)%20%3E0%20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20s.pop()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20current.data%2C%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20We%20have%20visited%20the%20node%20and%20its%20left%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20subtree.%20Now%2C%20it\u2019s%20right%20subtree\u2019s%20turn%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20current.right%20%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20done%20%3D%201%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0A%20%0A%22%22%22%20Constructed%20binary%20tree%20is%0A%20%20%20%20%20%20%20%20%20%20%20%201%0A%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%5C%0A%20%20%20%20%20%20%20%20%202%20%20%20%20%203%0A%20%20%20%20%20%20%20%2F%20%20%5C%0A%20%20%20%20%20%204%20%20%20%205%20%20%20%22%22%22%0A%20%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0A%20%0AinOrder(root)%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>inorder tree travesal without recursion &#8211; Using Stack is the obvious way to traverse tree without recursion.Below is an algorithm for traversing binary tree<\/p>\n","protected":false},"author":1,"featured_media":31288,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80125,80140],"tags":[81802,81803,81805,81800,80775,81801,81804,81909],"class_list":["post-27629","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binary-tree","category-binay-tree","tag-inorder-preorder-postorder-traversal-without-recursion-in-c","tag-inorder-traversal-with-recursion","tag-inorder-traversal-with-recursion-in-c","tag-inorder-traversal-without-recursion-and-stack","tag-postorder-traversal-java","tag-postorder-traversal-without-recursion","tag-postorder-traversal-without-recursion-and-stack","tag-preorder-traversal-without-recursion"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27629","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27629"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27629\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31288"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27629"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27629"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27629"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}