{"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 – 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> 
# Python program to do inorder traversal without recursion # A binary tree nodeclass Node:         # Constructor to create a new node    def __init__(self, data):        self.data = data         self.left = None        self.right = None # Iterative function for inorder tree traversaldef inOrder(root):         # Set current to root of binary tree    current = root     s = [] # initialze stack    done = 0         while(not done):                 # Reach the left most Node of the current Node        if current is not None:                         # Place pointer to a tree node on the stack             # before traversing the node's left subtree            s.append(current)                     current = current.left                   # BackTrack from the empty subtree and visit the Node        # at the top of the stack; however, if the stack is         # empty you are done        else:            if(len(s) >0 ):                current = s.pop()                print current.data,                         # We have visited the node and its left                 # subtree. Now, it's right subtree's turn                current = current.right              else:                done = 1 # Driver program to test above function """ Constructed binary tree is            1          \/   \\         2     3       \/  \\      4    5   """ root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5) inOrder(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n
 <\/p>\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":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}]}}