Binary search tree into array

Question

I'm stuck with returning BS tree put into an array. I guess the problem is that I'm not passing around the counter to determine where the next free index is (I was planning to make the counter as the first element of array to make it easier). Any suggestions?

  public int[] returnInOrderTraversal(){
       int[] arr = new int[getSize()+1];
  if (rootNode != null)
  {
      rootNode.returninOrderTraversal(arr);
  }
return arr;
   }


public void returninOrderTraversal(int[] arr){
  if(this.getLeftChild() != null)
  {
      this.getLeftChild().returninOrderTraversal(arr);

  }
  arr[arr[0]++] = this.getValue();
  if (this.getRightChild() != null)
  {
      this.getRightChild().returninOrderTraversal(arr);
  }  
}

score 0 · Answer 1 · edited May 23 '17 at 12:13

0

All you have to do is to change line:

arr[arr[0]++] = this.getValue();

to :

arr[++arr[0]] = this.getValue();

See How do the post increment (i++) and pre increment (++i) operators work in Java?

Also you can consider using ArrayList instead of array, you can get the same performance and you don't need to care about the index at all in this case. Just use add method.

edited May 23 '17 at 12:13

Community

1
1

answered Mar 12 '14 at 23:56

Viktor K.

2,670
2
19
30

Nope, still "java.lang.ArrayIndexOutOfBoundsException" – user2962334 Mar 13 '14 at 00:12
Could you add more code? How does getSize() method look like? – Viktor K. Mar 13 '14 at 00:22
There is some problem with your getSize() method, after you add 5 nodes, getSize() method returns 2. You are looking only to left or right child when calling getSize(), you have to look in both of them and add those two sizes... – Viktor K. Mar 13 '14 at 00:29
Thank you, I've changed it to a correct one, added print method public void printArray() { int[] arr = new int[getSize()+1]; returnInOrderTraversal(); System.out.println("Array: " + arr); } and now the output is [I@4187a8e0 instead of 1 2 4 5 9 12. Any ideas? – user2962334 Mar 14 '14 at 12:14

Binary search tree into array

1 Answers1