# Binary Tree Traversal — Non Recursive

1. Start from the root, visit the parent node before going into any sub-tree.
2. If the parent has only left child, go to the left.
3. If the parent has only right child, go to the right.
4. If the parent has both left and right children, hmm… we must go to the left child first, but we also need to do something to make sure some time later we can still reach the right child (otherwise the right tree is lost). So in this scenario, we will use a Stack to keep tracking the to-be-visited right nodes.
5. If the current node has no children (a left node), we should pop out the last added node from the Stack. It’s done if the Stack is empty.
`def visit(node):  # do whatever you want  pass  def preorder_non_recursive(root):  if not root:   return   stack = []  current = root  while current:    visit(current)    if current.left and current.right:      stack.append(current.right)      current = current.left    elif current.left:      current = current.left    elif current.right:      current = current.right    else:      current = stack.pop() if stack else None`
`def preorder_non_recursive(root):  if not root:   return   stack = [root]  while stack:    current = stack.pop()    visit(current)    if current.left and current.right:      stack.append(current.right)      # we must add the left node after the "right" here so      # the left is the next node to be visited      stack.append(current.left)    elif current.left:      stack.append(current.left)    elif current.right:      stack.append(current.right)`
1. The main difference from “preorder” is that we should visit the “parent” only after its left sub-tree is completely visited.
2. When reaching any node, we have to ask: are all of its left children visited?
3. To answer the above question, a straightforward solution is to use a HashSet to track visited nodes.
`def inorder_non_recursive(root):  if not root:    return  stack = [root]  visited = set()  while stack:    current = stack.pop()    if not current.left or current.left in visited:      visit(current)      visited.add(current)    else:      # add it back to the stack so it can be visited later      stack.append(current)    if current.left and current.right:      stack.append(current.right)      stack.append(current.left)    elif current.left:      stack.append(current.left)    elif current.right:      stack.append(current.right)`
• If the parent has left child, add the parent to the Stack and go to left.
• If the parent has no left child, visit the parent. Then go to the right child if it exists, otherwise go to the Stack top.
• If the parent has no children, go to the Stack top.
`def inorder_non_recursive(root):  if not root:    return  stack = [root]while stack:    current = stack.pop()    if current.left:      stack.append(current)      stack.append(current.left)      continue          visit(current)    if current.right:      stack.append(current.right)      continue            while stack:      node = stack.pop()      visit(node)      if node.right:        stack.append(node.right)        break`
`stack = []current = rootwhile stack or current:  if current and current.left:    stack.append(current)    current = current.left    continue  if not current:    current = stack.pop()  visit(current)  current = current.right`
1. Parent is the last to be visited (after left and right children).
2. If any node has right sub-tree, the root of the right sub-tree must be the last node visited immediately before the parent node. So we can say: if a node has a right child, it should be visited if and only if the right child node is visited.
3. After visiting a node, never go to any of its children again (the children must be already handled if the parent is visited).
4. Similar to inorder, whenever a node is popped out from the stack, its left sub-tree must be already finished (because we always prioritize handling the left sub-tree).
`stack = []current = rootlast_visited = Nonewhile stack or current:  if current and current.left:    stack.push(current)    current = current.left    continue  if not current:    current = stack.pop()  if current and current.right and current.right != last_visited:    stack.push(current)    current = current.right    continue  visit(current)  last_visited = current  current = None`

--

--

## More from Nardis

A music lover who can also writes code.

Love podcasts or audiobooks? Learn on the go with our new app.

## Nardis

A music lover who can also writes code.