Iterative Preorder

[hansmoolman]

Can anyone help.
I have written some recursive pre/postOrder methods for my BinartTree and they seem to be working fine. However, my iterative version of the preOrder doesnt seem to be working as I had expected. It simply prints all the values in the order they are added.

Can anyone spot where I am going wrong, or point me in the right direction.

My code is as follows:

import javax.swing.*;
import java.util.*;

public class BinaryTree {

    public static void main(String[] args) {
        
        BinaryTree tree = new BinaryTree();


        /**Then populate the Tree with some integer values         
          */
        int numberOfNumbers = Integer.parseInt(JOptionPane.showInputDialog(
                "Enter the total number of values you wish to add to the tree"));

        for (int i = 0; i < numberOfNumbers; i++)
        {
            int myNumbers = Integer.parseInt(JOptionPane.showInputDialog(
                    "Enter number " + (i + 1) + " to the tree"));

            tree.insert(myNumbers);
        }

        
        /**Allows the user to select a printing method for the BinaryTree
         */
        int choice = Integer.parseInt(JOptionPane.showInputDialog("Plese choose a display method: " +
                                                                  "\n1: Recursive preOrder" +
                                                                  "\n2: Recursive postOrder" +
                                                                  "\n3: Iterativeive preOrder")) ;

        System.out.println("The values are: ");
        /**User written methods to print the values of the tree
         * print(), printPreOrder(), printPostOrder() and printPreOrderIterative() traversals to print values
         * Depending on the users, choice, prints:
         *
         * tree.print();
         * tree.printPostorder();
         * tree.printPreorder();
         */
        if (choice == 1)
        {
            tree.printPreorder();
        }
        if (choice == 2)
        {
            tree.printPostorder();
        }
        if (choice == 3)
        {
            /**My printPreorderIterative() that prints all the user supplied values
             */
            tree.printPreorderIterative();
        }
    }


    // Root node pointer, will be null for an empty tree
    private Node root;
    
   private static class Node 
   {
       Node left;
       Node right;
       int data;
       
       /**Private inner class Constructor
        * Sets left and right node to null
        * and sets the Node data to be the newDate that is read in
        * @param newData
        */
       Node (int newData) 
       {
           left = null;
           right = null;
           data = newData;
       }
   }
   
   
   public BinaryTree() 
   {
       root = null;       
   }
   
   
   /**Returns true if the given target is in the binary tree. 
    * Uses a recursive helper.
    */
   public boolean contains(int data)
   {
       return (containsSub(root, data));
   }
   
   
   /**Given a node, recur down searching for the given data.
    * Recursive containsSub
    */ 
   private boolean containsSub(Node node, int data)
   {
       if (node == null)
       {
           return (false);
       }

       if (data == node.data)
       {
           return(true);
       }
       else if (data < node.data)
       {
           return (containsSub(node.left, data));
       }
       else
       {
           return (containsSub(node.right, data));
       }
   }
   
   
   /**Inserts the given data into the BinaryTree
    * Uses a recursive helper
    */
   public void insert(int data) 
   {
       root = insertSub(root, data);
   }

   /**Given a node pointer, recur down and insert the given data into the tree
    * Returns the new node pointer
    * Recursive insertSub
    */
   private Node insertSub(Node node, int data)
   {
       if (node == null)
       {
           node = new Node(data);
       }
       else
       {
           if (data <= node.data)
           {
               node.left = insertSub(node.left, data);
           }
           else
           {
               node.right = insertSub(node.right, data);
           }
       }

       return (node);                   //Return the new pointer to the caller
   }


   /** preOrderNonIterative() method
      * First, create a printPreorderIterative() that calls the preOrderIterative() method
    */
   public void printPreorderIterative()
   {
        preOrderIterative(root);
   }

   /**The preOrderIterative() method used to iterate through the tree
    * @param root
    */
   private void preOrderIterative(Node root)
   {
       Stack nodes = new Stack();
       nodes.push(root);
       Node currentNode;
       
       while (! nodes.isEmpty())
       {
           currentNode = (Node) nodes.pop();
           
           System.out.println("Node data: " + currentNode.data);

           Node right = currentNode.right;
           if (right != null)
               nodes.push(right);

           //System.out.println("Node data: " + currentNode.data);

           Node left = currentNode.left;
           if (left != null)
               nodes.push(left);  
       }
   }
}

[m00nchile]

The method itself looks ok at first glance. Try to make a tree, write it down on paper, then check if it's working correctly.
EDIT: I gave you code a run, and it seems to work fine.

[hansmoolman]

Thanks for the reply, yeah I stepped through the code and it seems to be fine, but shouldnt the preOrder method output values in a ascending order? Eg. if you input 1,6,5,3 - should the output not be 1,3,5,6? My recursive preOrder method seems to do this ok.

[m00nchile]

If you input 1, 6, 5, 3, the BST you get should be this:

  1
    \
     6
    /
   5
  /
3

Preorder is root, left right, so the output should be 1, 6, 5, 3. Now, if you'd change the input to 1,6, 7, 3, you'd get this:

  1
    \
     6
    /  \
   3    7

Now the preorder traversal would be 1,6,3,7. The traversal that ouputs a BST in ascending order is inorder, not preorder.

[hansmoolman]

Yeah that makes sense to me now thanks. I was going by a recursive preorder method that was given to us in class to compare my output too. Thanks again for clearing this up for me, much appreciated.