Make delicious recipes!

Pre-Order traversal without recursion


PreOrder traversal is the easiest to handle when recursion is not desired because it consumes the data before recursion.

void iterativePreorder(TreeNode root)
{
    if (root == NULL)
       return;
 
    Stack s = new Stack();
    nodeStack.push(root);
 
    while (s.empty() == false)
    {
        TreeNode node = s.pop();
        print (node);
 
        // Right child is pushed first so that during pop, left is processed first
        if (node.right)
            s.push(node.right);
        if (node.left)
            s.push(node.left);
    }
}


In-Order traversal without recursion

We print the leftmost grand child first, then its parent and then same logic for its right sibling.
Since, we do not have a parent pointer, we will need some auxiliary data structure to store parent pointer of each node.
As normal recursion also uses a stack, we can also use a stack for this purpose.

void inOrderNoRecursion(TreeNode curr)
{
    Stack<TreeNode> stack = new Stack<TreeNode>();

    while (true)
    {
        while (curr != null)
        {
            stack.push(curr);
            curr = curr.left;
        }
        if (stack.isEmpty())
            break;
        curr = stack.pop();
        System.out.println (curr.data);
        curr = curr.right;
    }
}
Note that this one uses 2 loops while pre-order used only a single loop.
The outer loop here allows the inner loop to exhaust current to null.

Post-Order traversal without recursion


To understand this, note the following:
  1. Pre-Order is D-L-R while Post-order is L-R-D
    Reverse of Pre-Order is R-L-D and if we swap R with L, it becomes L-R-D which is nothing but Post-Order
    Post-order (L-R-D) = reverse of pre-order (R-L-D) with positions of L and R swapped.

  2. If we empty one stack normally into another stack, the stack is reversed.

  3. So, if one more stack is used to empty stack of pre-order and positions of L and R are swapped, we will get post-order.


/************************************************************************************
  * Very much similar to the pre-order function above.
  * Only two differences:
  *   1) Where pre-order prints, post-order puts the value into another stack to reverse the order
  *   2) Order of left and right nodes is swapped
**************************************************************************************/
void postOrder (TreeNode root)
{
    Stack s1 = new Stack();
    Stack s2 = new Stack();

    s1.push (root);
    while (s1.empty() == false)
    {
        TreeNode node = s1.pop();
        s2.push (node); // pre-order prints at this point but post-order uses another stack to reverse the order

        if (node.left)
            s1.push (node.left); // pre-order pushes right first
        if (node.right)
            s1.push (node.right); //post-order pushes left in the last
    }

    while (s2.empty() == false) // print the modified pre-order in reverse to get the post-order
        print (s2.pop());
}

The stacks in the above code would run as follows for the below tree:

s1 = [9]
s2 = []

s1 = []
s2 = [9]

s1 = [5, 11]
s2 = [9]

s1 = [5, 10]
s2 = [9, 11]

s1 = [5]
s2 = [9, 11, 10]

s1 = [3, 7]
s2 = [9, 11, 10, 5]

s1 = [3, 6]
s2 = [9, 11, 10, 5, 7]

s1 = [3]
s2 = [9, 11, 10, 5, 7, 6]

s1 = []
s2 = [9, 11, 10, 5, 7, 6, 3]

s1 = [4]
s2 = [9, 11, 10, 5, 7, 6, 3]

s1 = []
s2 = [9, 11, 10, 5, 7, 6, 3, 4]
       9
     /   \
    /     \
   5       11
  /  \     /
 3    7   10
 \   /
  4 6
Expected postorder traversal is:
4, 3, 6, 7, 5, 10, 11, 9

Post order traversal keeps the entire left and right subtrees and starts printing in the end.

However, note that the above solution copies the entire tree into a stack before it starts printing.
So the space requirements of this solutions is O(n) where as other traversals had space requirements of O(h), h being the tree-height.
An O(h) solution for post-order is also given below.
(And it requires only a single stack!)

Post-order with single stack, stack-height limited to tree-height


Main idea in this traversal is that we use a prev variable to keep track of the last node visited.
This variable helps us know if we are going down the tree or coming up the tree.
void postOrderNoRecursion(TreeNode root)
{
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode prev = null;

    stack.push(root);

    while (!stack.isEmpty())
    {
        TreeNode current = stack.peek();

        // Just think about going down the tree in this "if"
        // block, either left side or the right side
        //  (but not both sides)
        // If a node has both left and right children, this "if" block
        // will put only the left in the stack
        if (prev == null || prev.left==current || prev.right==current)
        {
            if (current.left != null) // We prefer to traverse the left side
            {
                stack.push(current.left);
            }
            //  If both sides are present, right child is NOT pushed onto stack at this point
            // That right child is handled on line 39 after we have already finished left traversal
            else if (current.right != null) 
            {
                stack.push(current.right);
            }
            else
            {
                System.out.print(current.data + ", ");
                stack.pop();
            }
        }
        else if (current.left == prev) // Coming up from the left side
        {
            if (current.right != null)
            {
                stack.push(current.right);
            }
            else
            {
                System.out.print(current.data + ", ");
                stack.pop();
            }
        }
        else if (current.right == prev) // Coming up from the right side
        {
            System.out.print(current.data + ", ");
            stack.pop();
        }
        
        prev = current;
    }
}

To make it easy to understand, note the following interesting properties of the above solution:

  1. The first "if" block populates only one child in the stack, either left or right (but not both).
  2. The second "if" block knows that we are coming up from the left side and since #1 did not populate right child in the stack, it does so.
    So its code is just a copy of lines 25-33.
  3. The third "if" block knows that we are coming up from the right side and since there is no other child left to populate, it just prints the node.
    So its code is just a copy of lines 29-33.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal