How to convert a red black BST into an array?

Question

I want to convert a red black BST into an array but something goes wrong and I can't figure out what. Here is a snippet of code I used to do this:

public T[] toArray() {
    T[] array = (T[]) Array.newInstance(clazz, count);

    inOrder(root, array, 0);

    return array;
}

private void inOrder(Node<T> node, T[] array, int i) {
    if (node != null) {
        inOrder(node.leftChild(), array, i);
        array[i++] = node.data();
        inOrder(node.rightChild(), array, i);
    }
}

After inserting numbers from 10 to 200 in ascending order, the output looks like this (I used preorder traversal to see if the tree stay balanced):

[80, 40, 20, 10, 30, 60, 50, 70, 120, 100, 90, 110, 140, 130, 160, 150, 170, 180]

But when I call toArray() method, I get this:

80 120 140 160 170 180 null null null null null null null null null null null null 

What did I do wrong here?

Answer 1

It looks like only the root and the right-most children are getting copied to the array. Your i value is being changed in each recursive call, but it's not getting updated when the recursive call ends.

Let's say your tree is:

    80
   /  \
  40  120

Your array is of size 3.

Your first call:

• i is 0.
• Recursive call to inOrder with the left child:
  • i is 0.
  • Recursive call to inOrder with the left child, which is null.
  • Store the element 40 at element 0, increasing i to 1.
  • Recursive call to inOrder with the right child, which is null.
  • Return.
• Here, i is 0 still!
• Store the element 80 at element 0, increasing i to 1.
• Recursive call to inOrder with the right child:
  • i is 1.
  • Recursive call to inOrder with the left child, which is null.
  • Store the element 120 at element 1, increasing i to 2.
  • Recursive call to inOrder with the right child, which is null.
  • Return.
• Return.

The result is [80, 120, null].

Have each recursive call return the value of i back to its caller, so that i stays updated at all levels of recursion.

private int inOrder(Node<T> node, T[] array, int i) {
    if (node != null) {
        i = inOrder(node.leftChild(), array, i);
        array[i++] = node.data();
        i = inOrder(node.rightChild(), array, i);
    }
    return i;
}