{"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 – Inorder Tree Traversal without Recursion"},"content":{"rendered":"

Using Stack <\/a>is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this <\/a>for step wise step execution of the algorithm.<\/p>\n

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
Let us consider the below tree for example<\/p>\n
            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
 
 <\/div> 
\/\/ non-recursive java program for inorder traversal \/* importing the necessary class *\/import java.util.Stack; \/* Class containing left and right child of current  node and key value*\/class Node {     int data;    Node left, right;     public Node(int item) {        data = item;        left = right = null;    }} \/* Class to print the inorder traversal *\/class BinaryTree {     Node root;     void inorder() {        if (root == null) {            return;        }                \/\/keep the nodes in the path that are waiting to be visited        Stack<Node> stack = new Stack<Node>();        Node node = root;                 \/\/first node to be visited will be the left one        while (node != null) {            stack.push(node);            node = node.left;        }                 \/\/ traverse the tree        while (stack.size() > 0) {                       \/\/ visit the top node            node = stack.pop();            System.out.print(node.data + " ");            if (node.right != null) {                node = node.right;                                 \/\/ the next node to be visited is the leftmost                while (node != null) {                    stack.push(node);                    node = node.left;                }            }        }    }     public static void main(String args[]) {                 \/* creating a binary tree and entering          the nodes *\/        BinaryTree tree = new BinaryTree();        tree.root = new Node(1);        tree.root.left = new Node(2);        tree.root.right = new Node(3);        tree.root.left.left = new Node(4);        tree.root.left.right = new Node(5);        tree.inorder();    }}<\/code><\/pre> <\/div>\n
Time Complexity: O(n)<\/p>\n
Output:<\/p>\n
 4 2 5 1 3<\/pre>\n","protected":false},"excerpt":{"rendered":"
inorder tree travesal without recursion – 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}]}}