Complete Binary Tree in Java (ArrayList implementation)

Question

inOrder, postOrder, and preOrder seem to be printing extra numbers. Why is this happening?

import java.util.*;

public class CBT{

  private ArrayList tree;

  public CBT(){

tree = new ArrayList();

  }

  //traversals

  public void inOrder(){

   // left, root, right

   for(int i = 0; i < tree.size()-1; i++) {

   // find start position (left)

   int left = 2*i +1;

     if(tree.indexOf(left) != -1) System.out.println(tree.indexOf(left));

   // parent of left: index of (k-1/2) 

   int parent = (i-1)/2;

     if(tree.indexOf(parent) != -1 && tree.indexOf(parent) != 0) System.out.println(tree.indexOf(parent));

   

   // visit right subtree (2k+2)

   int right = 2*i+2;

     if(tree.indexOf(right) != -1) System.out.println(tree.indexOf(right));

   }

//   if(i*2+1<tree.size()) inOrder(i*2+1);

//     System.out.print(tree.get(i)+" ");

//     if (i*2+2<tree.size()) inOrder(i*2+2);

     

  }

  public void inorder(int n) {

   if(tree.size() < n) return;

   inorder(2*n+1);

   System.out.println(tree.get(n));   

   inorder(2*n+2);

  }

   

  public void preOrder() {

   // root, left, right

   if(tree.size() == 0) return; 

     for(int i =0; i <tree.size()-1 ; i++) {

     System.out.println(tree.indexOf(i));

   int left = 2*i + 1;

   if(tree.indexOf(left) != -1) System.out.println(tree.indexOf(left));

   int right = 2*i + 2;

   if(tree.indexOf(right) != -1) System.out.println(tree.indexOf(right));

     }

  }

  public void postOrder() {

   // left, right, root

   if(tree.size() == 0) return; 

   for(int i = 0; i < tree.size() -1; i++) {

   // find start position (leftmost )

   int left = 2*i +1;

   if(tree.indexOf(left) != -1) System.out.println(tree.indexOf(left));

   // go through parent to visit right (2k+2)

   int parent = (i-1)/2;

   int right = 2*parent +2;

   if(tree.indexOf(right) != -1) System.out.println(tree.indexOf(right));

   // go back to parent (k-1/2)

   if(tree.indexOf(parent) != -1) System.out.println(tree.indexOf(parent));

   }

  }

  public void breadthFirst() {

   // go left to right

   if(tree.size() == 0) return; 

   for (int i = 0; i < tree.size(); i++) {

   System.out.println(tree.get(i));

   }

  }

  //accessors

  public boolean contains(Object o) {

    if (tree.size() == 0) return false; 

    for(int i = 0; i < tree.size(); i++) {

    if(tree.get(i) == o) return true;

    }

    return false; 

  }

  //mutators

  public void add(Object o){

   tree.add(o);

  }

   

  public boolean remove(Object o){

   if(tree.size() == 0) return false;

   for(int i = 0; i < tree.size(); i++) {

if(tree.get(i) == o) {

tree.remove(o);

return true; 

}

}

   return false;

  }

  public static void main(String[] args){

   CBT cbt = new CBT();

int[] vals = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for (int v: vals) cbt.add(v);

System.out.print("In order: ");

cbt.inOrder();

System.out.println();

System.out.print("Pre order: ");

cbt.preOrder();

System.out.println();

System.out.print("Post order: ");

cbt.postOrder();

System.out.println("Breadth First: ");

cbt.breadthFirst();

  }

}

Answer 1

inOrder(), preOrder(), postOrder() should not iterate over the array.

For each you need a recursive method like inorder(int n).

Then inorder() merely calls inorder(0), because index 0 contains the root of the tree.

After you make these changes you will encounter other problems.

For example,

- The termination condition of inorder(int n) should be "<=", not "<".

- The methods contains(Object o) and remove(Object o) should probably use the equals() method, not "==".

- The remove(Object o) instead of removing anything goes into infinite recursion.