Abstract Scribbles

Non Recursive (Iterative) Binary Tree Traversal

Recursive binary tree traversals have been documented everywhere and is quite trivial to solve. After a bit of web crawling, my favorite article documenting this was found here.

Non Recursive tree traversal is much more complicated than its recursive counterpart and requires a stack. Every time we decide to postpone an operation on a node, we need to push that node onto the stack.

Post order Non Recursive Binary Tree Traversal

Order: Left, Right, Root.

Key: In addition to a stack, we need two pointers - a current node and previous node pointer that help us determine which direction we are traversing. The direction will help us as follows:

• If we are going downward, we either need to keep going downward or print if we cannot go downward anymore.
• If we are going upward from the left, we need to explore the right. If we are going upward from the right, we are done analyzing the right and need to print the root and go further upward.

The algorithm without error handling:

1. curr = prev = root
2. Initialize stack
3. while (true)
4.     if ( curr is prev or a child of prev) //Traversing downwards
5.         if (curr is a parent) //More traversing to do
6.             stack.push(curr)
7.             prev = curr
8.             curr = curr.left
9.         else //curr is an orphan: go upward
10.             print (curr)
11.             prev = curr
12.             curr = stack(top)
13.     if ( curr.left = prev)  //Traversing upwards from the left: go right
14.         prev = curr 
15.         curr = curr.right
16.     if ( curr.right = prev) //Traversing upwards from the right: Print & go upward
17.         print (curr)
18.         stack.pop()
19.         prev = curr
20.         curr = stack.top()
21.     if (stack.IsEmpty && curr == null) return