How to fill an array with node elements from a binary search tree, in ascending order?

Question

In a school assignment I'm supposed to complete a method that should return an array of node elements in ascendig order. The nodes are assembled in a binary search tree, so to sort them correct, I got a tip to create a recursive method to do the job.

The problem is that this doesn't even yield all the elements in the collection according to the test output (java.lang.AssertionError: toArray() does not return all the elements in the collection.)

I couldn't come up with any other way to deal with the array, and I'm not quite sure if the recursion even works. Any help is much appreciated. Below is my code:

public class BinarySearchTree<E extends Comparable<E>> implements
    IfiCollection<E> {

    Node root;
    Node current;
    int size = 0;
    int i = 0;

    public class Node {
    E obj;
    Node left, right;

    public Node(E e) {
        obj = e;
    }

    } // END class Node

    [...]

    public E[] toArray(E[] a) {

    Node n = root;

    a = sort(n, a);
    return a;

    }

    public E[] sort(Node n, E[] a) { //, int idx, E[] a) {

    if (n.left != null) {
        current = n.left;
        sort(current, a);
    }


    a[i] = current.obj;
    i++;

    if (n.right != null) {
        current = n.right;
        sort(current, a);
        }

    return a;

    } // END public Node sort

    [...]

} // END class BinarySearchTree

Test output:

java.lang.AssertionError: toArray() does not return all the elements in the collection.: TestPerson("Bender").compareTo(TestPerson("Fry")) == 0 expected:true but was:false at inf1010.assignment.IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:74) at inf1010.assignment.IfiCollectionTest.assertCompareToEquals(IfiCollectionTest.java:83) at inf1010.assignment.IfiCollectionTest.assertCompareToEqualsNoOrder(IfiCollectionTest.java:100) at inf1010.assignment.IfiCollectionTest.toArray(IfiCollectionTest.java:202)

protected void assertCompareToEquals(TestPerson actual,
        TestPerson expected, String msg) {
            assertTrue(actual.compareTo(expected) == 0, String.format( // l:74
            "%s: %s.compareTo(%s) == 0", msg, actual, expected));
}

    [...]

protected void assertCompareToEquals(TestPerson[] actual,
        TestPerson[] expected, String msg) {
    for (int i = 0; i < actual.length; i++) {
        TestPerson a = actual[i];
        TestPerson e = expected[i];
        assertCompareToEquals(a, e, msg); // l:83
    }
}

    [...]

protected void assertCompareToEqualsNoOrder(TestPerson[] actual,
        TestPerson[] expected, String msg) {
    assertEquals(actual.length, expected.length, msg);

    TestPerson[] actualElements = new TestPerson[actual.length];
    System.arraycopy(actual, 0, actualElements, 0, actual.length);

    TestPerson[] expectedElements = new TestPerson[expected.length];
    System.arraycopy(expected, 0, expectedElements, 0, expected.length);

    Arrays.sort(expectedElements);
    Arrays.sort(actualElements);

    assertCompareToEquals(actualElements, expectedElements, msg); // l:100
}

    [...]

@Test(dependsOnGroups = { "collection-core" },
    description="Tests if method toArray yields all the elements inserted in the collection in sorted order with smallest item first.")
public void toArray() {
    TestPerson[] actualElements = c.toArray(new TestPerson[c.size()]);

    for (int i = 0; i < actualElements.length; i++) {
        assertNotNull(actualElements[i],
                "toArray() - array element at index " + i + " is null");
    }

    TestPerson[] expectedElements = allElementsAsArray();
    assertCompareToEqualsNoOrder(actualElements, expectedElements, // l:202
            "toArray() does not return all the elements in the collection.");

    Arrays.sort(expectedElements);
    assertCompareToEquals(actualElements, expectedElements,
            "toArray() does not return the elements in sorted order with "
                    + "the smallest elements first.");


    TestPerson[] inArr = new TestPerson[NAMES.length + 1];
    inArr[NAMES.length] = new TestPerson("TEMP");
    actualElements = c.toArray(inArr);
    assertNull(actualElements[NAMES.length],
            "The the element in the array immediately following the "
            + "end of the list is not set to null");
}

I don't know if I should post more of the test code, it's quite extensive, and it might be a little too much for one post?

Answer 1

Ok, I think the problem is your use of the "global" variable current. The way it is set, doesn't make much sense. You don't need to anyway, because the "current" Node is the one that is provided in the parameters.

Also you should consider renaming your function. You aren't sorting anything here, just collecting the contents of the tree, so a name such as collect would be more suitable.

public E[] toArray(E[] a) {
  Node n = root;
  a = collect(n, a);
  return a;
}

public E[] collect(Node n, E[] a) {

  if (n.left != null) {
    // If there is a left (smaller) value, we go there first
    collect(n.left, a);
  }


  // Once we've got all left (smaller) values we can
  // collect the value of out current Node.
  a[i] = n.obj;
  i++;

  if (n.right != null) {
    // And if there is a right (larger) value we get it next
    collect(n.right, a);
  }

  return a;
}

(Disclaimer: I haven't tested this)

---

Alternative implementation without the global index:

public E[] toArray(E[] a) {
  Node n = root;
  collect(n, a, 0);
  return a;
}

public int collect(Node n, E[] a, int i) {

  if (n.left != null) {
    // If there is a left (smaller) value, we go there first
    i = collect(n.left, a, i);
  }


  // Once we've got all left (smaller) values we can
  // collect the value of out current Node.
  a[i] = n.obj;
  i++;

  if (n.right != null) {
    // And if there is a right (larger) value we get it next
    i = collect(n.right, a, i);
  }

  return i;
}

Answer 2

I see you have the code

if (n.left != null) {
        current = n.left;
        sort(current, a);
  }

but I can't seem to find at which point you set current back at the current node so that when you do

a[i] = current.obj;

you get the correct result. That's probably why you're not getting all the results. In any case I don't see (at least from the code fragments you have posted) why current needs to be a class variable and not just declared in the sort method. In general you shouldn't be using class variables if you don't really need them.

Edit: You can either set current back to the node you are processing after calling sort on the left child like this

current = n;
a[i] = current.obj;
i++;

Or not use current at all in which case you'd have something like

if (n.left != null)
    sort(n.left, a);
a[i] = n.obj;
i++;
if (n.right != null)
    sort(n.right, a);

Answer 3

http://cs.armstrong.edu/liang/intro8e/html/BinaryTree.html

The easiest way to do what you are looking for is to traverse the tree inorder and append to an ArrayList. To get the array you can call the .toArray() method of the arrayList.

If you can't use an arraylist, declare an index and an array outside the inordertraversal and increment, you will need to know how many elements are in the tree to declare your array.

pseudo code:

variables:
arraysize = root.count()
E[] inOrderNodeArray = new E[arraysize]
int index = 0

inorder traversal:
void inorder(Node n) {
    if (n) {
        inorder(n.left)
        inOrderNodeArray[index] = n
        index++
        inorder(n.right)
    }
}

Answer 4

I think where you are confused is that if you check out how a binary search tree works, is that it is always sorted. You start at your root node, and then as you insert a new node, it inserts it into the appropriate position (i.e. to the left or the right) depending on the values. So you should not have to call sort to begin with. So I would start there, and read up on binary search trees. For example wikipedia has a decent article.

Update: Ignore my comment you should not need to do that either. Say you insert 8, 3, 7, 9, 12, 2, 10, 1 into the tree in that order. It should end up looking like this:

      8
     / \
    3   9
   / \   \
  2   7   12
 /       /
1       10

If you look at it that means to get them in order, start at the root, then if it has a node to the left got to the left, if not, return itself, and go to the right if it has a value. Repeating this for each node you encounter.