Difference Between Two Iterative Solutions for PreOrder Traversal of a Binary Tree

Question

As of right now, I'm trying to get a intuitive understanding of recursion by also working on using the Stack object in Java. On GeeksForGeeks, they have practice problems on traversal methods on a binary tree. Currently I'm on PreOrder and while I've figured out the recursive solution, the iterative solution is proving to be quite troublesome to come up with. When I pulled up the actual answer to the problem, I found that my code is practically identical to the solution code. I've been going back and forth for a while trying to figure out why my Iterative solution for a PreOrder traversal is incorrect compared to the actual solution but thought that maybe I need a third set of more experienced eyes to tell me why I'm wrong.

Here's the url to the problem and the online compiler: https://practice.geeksforgeeks.org/problems/preorder-traversal/1

Here's my code:

void preorder(Node root)
{
   // Your code goes here
   if(root == null) return;
   Stack<Node> stack = new Stack<Node>();

   stack.push(root);
   while(!stack.isEmpty()) {
       Node cur = stack.pop();
       System.out.print(cur.data + " ");

       if(cur.left != null) {
           stack.push(cur.left);
       }
       if(cur.right != null) {
           stack.push(cur.right);
       }
   }
}

Here's the solution code:

void preorder(Node root) { 

    // Base Case 
    if (root == null) { 
        return; 
    } 

    // Create an empty stack and push root to it 
    Stack<Node> nodeStack = new Stack<Node>(); 
    nodeStack.push(root); 

    /* Pop all items one by one. Do following for every popped item 
     a) print it 
     b) push its right child 
     c) push its left child 
     Note that right child is pushed first so that left is processed first 
*/
    while (nodeStack.empty() == false) { 

        // Pop the top item from stack and print it 
        Node mynode = nodeStack.peek(); 
        System.out.print(mynode.data + " "); 
        nodeStack.pop(); 

        // Push right and left children of the popped node to stack 
        if (mynode.right != null) { 
            nodeStack.push(mynode.right); 
        } 
        if (mynode.left != null) { 
            nodeStack.push(mynode.left); 
        } 
    } 
} 

Answer 1

Preorder traversal for a binary tree is Visit,Left and Right.

Your code is not similar to solution's code.

You need to push right child first to the stack and then the left child to bring left child on top of the stack and then visit that child. Hence, modify your code as shown below-

void preorder(Node root)
{
   // Your code goes here
   if(root == null) return;
   Stack<Node> stack = new Stack<Node>();

   stack.push(root);
   while(!stack.isEmpty()) {
       Node cur = stack.pop();
       System.out.print(cur.data + " ");

       if(cur.right != null) {
           stack.push(cur.right);
       }

       if(cur.left != null) {
           stack.push(cur.left);
       }

   }
}