Inorder Tree Traversal without Recursion

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

1) Create an empty stack S. 2) Initialize current node as root 3) Push the current node to S and set current = current->left until current is NULL 4) If current is NULL and stack is not empty then a) Pop the top item from stack. b) Print the popped item, set current = popped_item->right c) Go to step 3. 5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example

# Python program to perform iterative preorder traversal # A binary tree node class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None # An iterative process to print preorder traveral of BT def iterativePreorder(root): # Base CAse if root is None: return # create an empty stack and push root to it nodeStack = [] nodeStack.append(root) # Pop all items one by one. Do following for every popped item # a) print it # b) push its right child # c) push its left child # Note that right child is pushed first so that left # is processed first */ while(len(nodeStack) > 0): # Pop the top item from stack and print it node = nodeStack.pop() print node.data, # Push right and left children of the popped node # to stack if node.right is not None: nodeStack.append(node.right) if node.left is not None: nodeStack.append(node.left) # Driver program to test above function root = Node(10) root.left = Node(8) root.right = Node(2) root.left.left = Node(3) root.left.right = Node(5) root.right.left = Node(2) iterativePreorder(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Time Complexity: O(n)

Output: 4 2 5 1 3

My codes:

class Solution3(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ans = [] s = [] t = root while t is not None or s: while t is not None: s.append(t) t = t.left if t.left is not None else t.right t = s.pop() ans += [t.item] print ans if s and s[-1].left == t: t = s[-1].right else: t = None return ans def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ans = [] s = [] t = root while t is not None or s: while t is not None: ans += [t.item] s.append(t.right) t = t.left t = s.pop() return ans def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ans = [] s = [] t = root while t is not None or s: while t is not None: s.append(t) t = t.left t = s.pop() ans += [t.item] t = t.right return ans

Reference:

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/