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 = root
while 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 = root
last_visited = None
while 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store