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


1 comment:

  1. Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Front end developer learn from Javascript Training in Chennai . or learn thru JavaScript Online Training India. Nowadays JavaScript has tons of job opportunities on various vertical industry.

    ReplyDelete