Thursday, September 8, 2011

Inorder Traversal Without Recursion using Stacks

Logic for Inorder traversal without recursion, using a stack.

Pseudo code ::


inOrderTraverse (Node root)  {

-> Stack s
-> Node n = root

-> pushLeftNodesToStack (s, n)

-> while( s NOT empty)

         -> v = s.pop
         -> print (v)
         -> v = v.right
         -> pushLeftNodesToStack (s, v)

}



// separate function - passed a node, push that node and all its lefts to stack.

pushLeftNodesToStack(Stack s, Node n)  {

-> while (n != null)

         -> s.push (n);
         ->  n = n.left;

}


References -

http://geeksforgeeks.org/archives/5592
http://codepad.org/QEVUNzYU


No comments:

Post a Comment