{"id":27628,"date":"2018-04-04T19:36:53","date_gmt":"2018-04-04T14:06:53","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27628"},"modified":"2018-09-16T14:23:49","modified_gmt":"2018-09-16T08:53:49","slug":"java-program-inorder-tree-traversal-without-recursion","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-inorder-tree-traversal-without-recursion\/","title":{"rendered":"Java Program &#8211; Inorder Tree Traversal without Recursion"},"content":{"rendered":"<p>Using <a href=\"http:\/\/en.wikipedia.org\/wiki\/Stack_%28data_structure%29\" target=\"_blank\" rel=\"noopener\">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\" target=\"_blank\" rel=\"noopener\">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=\u201djava\u201d manual=\u201d%2F%2F%20non-recursive%20java%20program%20for%20inorder%20traversal%0A%20%0A%2F*%20importing%20the%20necessary%20class%20*%2F%0Aimport%20java.util.Stack%3B%0A%20%0A%2F*%20Class%20containing%20left%20and%20right%20child%20of%20current%20%0A%20node%20and%20key%20value*%2F%0Aclass%20Node%20%7B%0A%20%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20left%2C%20right%3B%0A%20%0A%20%20%20%20public%20Node(int%20item)%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20item%3B%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Class%20to%20print%20the%20inorder%20traversal%20*%2F%0Aclass%20BinaryTree%20%7B%0A%20%0A%20%20%20%20Node%20root%3B%0A%20%0A%20%20%20%20void%20inorder()%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2Fkeep%20the%20nodes%20in%20the%20path%20that%20are%20waiting%20to%20be%20visited%0A%20%20%20%20%20%20%20%20Stack%3CNode%3E%20stack%20%3D%20new%20Stack%3CNode%3E()%3B%0A%20%20%20%20%20%20%20%20Node%20node%20%3D%20root%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2Ffirst%20node%20to%20be%20visited%20will%20be%20the%20left%20one%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20stack.push(node)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.left%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20traverse%20the%20tree%0A%20%20%20%20%20%20%20%20while%20(stack.size()%20%3E%200)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20visit%20the%20top%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20stack.pop()%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(node.right%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.right%3B%0A%20%20%20%20%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%20%20%20%20%2F%2F%20the%20next%20node%20to%20be%20visited%20is%20the%20leftmost%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20stack.push(node)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.left%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%20%7B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20creating%20a%20binary%20tree%20and%20entering%20%0A%20%20%20%20%20%20%20%20%20the%20nodes%20*%2F%0A%20%20%20%20%20%20%20%20BinaryTree%20tree%20%3D%20new%20BinaryTree()%3B%0A%20%20%20%20%20%20%20%20tree.root%20%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20%20tree.root.left%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20tree.root.right%20%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.left%20%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20%20tree.root.left.right%20%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20tree.inorder()%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Time Complexity: O(n)<\/p>\n<p>Output:<\/p>\n<pre> 4 2 5 1 3<\/pre>\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":31291,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[81802,81803,81805,81800,80775,81801,81804,81909],"class_list":["post-27628","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","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\/27628","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=27628"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27628\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31291"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27628"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27628"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27628"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}