CODEWITHSUNDEEP
algorithmdata-structuresbinary-treepreorder
Rohit Singh
Rohit Singh

Reputation: 18202

Recursion does not stop in Preorder Traversal

I am writing a recursive program to traverse a BinaryTree in Preorder. Here is the BinaryTree class definition

public class BinaryTree {

   private int data;
   private BinaryTree left,right;

   public BinaryTree(int data){
      this.data = data;
      this.left = null;
      this.right = null;
   }

   public int getData(){
      return data;
   }

   public BinaryTree getLeft() {
      return left;
   }

   public BinaryTree getRight() {
      return right;
   }

   public void setData(int data) {
      this.data = data;
   }

   public void setLeft(BinaryTree left) {
      this.left = left;
   }

   public void setRight(BinaryTree right) {
      this.right = right;
   }

}

Here is my test program

public class TreeTest {

   public static void main(String[] args){

      TreeTest treeTest = new TreeTest();
      treeTest.preTraversal(treeTest.getBinaryTree());
   }

   public void preTraversal(BinaryTree binaryTree){

      while(binaryTree!=null){
          System.out.println(binaryTree.getData()+" ");
          preTraversal(binaryTree.getLeft());
          preTraversal(binaryTree.getRight());
      }
   }

   //Tree creation 
   public BinaryTree getBinaryTree(){
       BinaryTree root = new BinaryTree(1);
       BinaryTree node2 = new BinaryTree(2);
       BinaryTree node3 = new BinaryTree(3);
       root.setLeft(node2);
       root.setRight(node3);
       return root;
   }

}

The problem is that the program never stops. Here is the output.

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Upvotes: 0

Views: 58

Answers (2)

CiaPan
CiaPan

Reputation: 9570

The culprit is this instruction:

while(binaryTree!=null){

– it tests the binaryTree variable again and again, but the variable is never changed, so the loop never ends.

A cure: replace while with if:

public void preTraversal(BinaryTree binaryTree){
   if(binaryTree!=null){
       System.out.println(binaryTree.getData()+" ");
       preTraversal(binaryTree.getLeft());
       preTraversal(binaryTree.getRight());
   }
}

Upvotes: 3

Devi Khositashvili
Devi Khositashvili

Reputation: 576

I GUESS YOU NEED IF INSTEAD OF WHILE:

   public void preTraversal(BinaryTree binaryTree){
      if(binaryTree != null){
          System.out.println(binaryTree.getData()+" ");
          preTraversal(binaryTree.getLeft());
          preTraversal(binaryTree.getRight());
      }
   }

Upvotes: 1

Related Questions