Binary Tree Traversal — Non Recursive

This article talks about recursive solutions of binary tree traversal.

Preorder

Thinking:

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.

Why it works?

Only points 4 and 5 need some explanation. We push the right node to the stack only if the parent has both children. Every time after visiting a leaf node, the Stack top will be the right child of the current left node’s closest parent (or ancestor more accurately). Note that we never need to push the “current node” or “left node” to the Stack since they are always immediately visited or will be visited soon in the next iteration.

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

Another slightly different style is to always track the “current node” using the Stack top. It looks like this:

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)

In this style, we always get the “current node” to visit from the Stack top at the beginning of each iteration, so there’s no need to track the “current node” outside of the loop. The last else block is also gone.

Inorder

Thinking:

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)

This obviously takes more space. In the above code, we have to add the “current” node back to the Stack when it’s not time to visit it yet. Then when is it popped out again?

The answer is when all of its left children are visited. To understand why, you should try to view the left sub-tree as an isolated tree in the program. i.e. when you push the parent back to the Stack, you should forget about it, because all you’re doing next is to handle the left tree. After the left tree is done, you will get to the “parent” again, and now it’s the time to visit it.

We still don’t need to worry about the right tree too much since it’s to be handled only after its parent is visited.

So we can simplify the logic as:

• 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.

What to do when it goes to the Stack top? Obviously we should visit it now. And we shouldn’t go to the left tree any more. So we should go to right (if right child exists) or continue popping out the Stack (if right child doesn’t exist).

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

We should use a small technique to get rid of the inner while-loop.

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

Postorder

Thinking:

Obviously, we could also use a HashSet to remember the visited nodes and it’s fairly easy to implement this logic. But we should be able to do better.

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

Please leave a comment if you see any mistake or want to say anything. Thanks for reading!