Non Recursive Inorder Traversal

[sbharathind]

public static void nonRecursiveInorder(Node node)
    {
        Stack<Node> st=new Stack();
        st.push(node);
        Node temp;
        while(!st.isEmpty())
        {
            temp=st.peek();
            if(temp.left!=null && temp.left.visited==false)
                st.push(temp.left);
            else 
            {
                if(temp.left==null && temp.right!=null && temp.right.visited==false)
                {
                    System.out.print(" "+temp.value);
                    temp.visited=true;
                    st.pop();
                    st.push(temp.right);
                }
                else 
                {
                    if(temp.left!=null && temp.left.visited==true && temp.right!=null && temp.right.visited==false)
                    {
                        System.out.print(" "+temp.value);
                        temp.visited=true;
                        st.pop();
                        st.push(temp.right);
                    }
                else
                {
                    System.out.print(" "+temp.value);
                    temp.visited=true;
                    st.pop();
                }
            }
        }
        }
    }

[sbharathind]

The above is my Program in Java for Non-rECURSIVE INORDER Traversal is the above code correct ? I checked with examples of my own I didnt find any mistakes. Can u pls check and let me know if it is correct

[tux4life]

Your algorithm is more complex than it should be, compare with the following:

iterativeInorder(node)
  parentStack = empty stack
  while not parentStack.isEmpty() or node != null
    if node != null then
      parentStack.push(node)
      node = node.left
    else
      node = parentStack.pop()
      visit(node)
      node = node.right

(Source: Tree Traversal - Wikipedia)

[devinnrock]

i am goin to try this coading....i hope it would be work.

[tux4life]

``You use class Stack, this is a legacy datastructure in Java, and it extends from Vector (another legacy datastructure - still used in Swing however), my personal recommendation would be not to use it. Prefer something more recent like ArrayDeque.

On an interesting note:

• "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." (Java API - ArrayDeque))

• "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class." (Java API - Stack)`

(Source: one of my earlier posts)

[sbharathind]

@tux4life: I will try with Array Deque and yeah I knew my coding was much complexer than what it shuld be. . .I was just trying to write code on my own to test whether am I getting it correct or not. ..And thanks for the Info. .But could you say would my code have been Fine ? Though complex ?