Trying to Convert Binary Search Tree to Array (returns Null)

Question

I want to convert my binary search tree into array (using in order traversal).

to Do this I have 3 methods.

Issue: java.lang.NullPointerException in the method 1 System.out.print() call. However returns 4 elements successfully (2 are null hence this error but why?!)

Class (1 main) method 1 (call method)

 public void top() {
    array[] unsortedList = this.bookList.returnBSTAsArray(6); // 6 is the number of nodes in tree
     for (Book book: unsortedList) {
         System.out.println("--> Title: " + book.title());
     }

class (2) method 2

// traverse BST in order and return an array of books 
public Book[] returnBSTAsArray(int totalLength) {
    Book[] list = new Book[totalLength];
    int index = 0;

    storeInOrder(this.root, list, index);  // root is node accessible to this class

    return list;
}

Class (2) method 3 - the interesting method that does the in order traverse

 private Book[] storeInOrder(Node root, Book[] array, int index) {
        if (root == null)
            return null;
        storeInOrder(root.leftChild, array, index);
        array[index++] = root.movie;
        storeInOrder(root.rightChild, array, index);

        return array;
    }

Answer 1

Java is a "pass by value" language. Hence (generaly speaking), any change to an argument value in a function won't be visible by the caller.

The storeInOrder function is the problem. It is written as if changes to the index arg will be visible by the caller.

This assumption is incorrect.

Moreover, it returns the array, but as an array is indeed a reference, it is not changed in the method (but it CONTENT is), hence there is no need to return the array as a result.

Hence, a better profile would be for storeInOrder to take and return the index of the first available cell in the array.

/**
 * insert the elements of the bst (denoted by root) into array,
 * starting at index (the first available position in array) and
 * returns the first available position after insertion)
 * pre-conditions : 
 *    - root is a bst containing n elements
 *    - array contains enough available cells
 *    - index = i0
 * post-conditions
 *    - tree is unchanged
 *    - array[i0..i0+n-1] contains elements of the bst
 *    - functions returns i0+n
 */
private int storeInOrder(Node root, Book[] array, int index) {
    if (root == null)
        return index;
    // then call on left, add root, call on right...
    int i = storeInOrder(root.leftChild, array, index);
    array[i] = root.movie;
    return storeInOrder(root.rightChild, array, i+1);
}

NOTA: if you want the array in Book's order, just change the order of the recursive calls to get the prefix left right traversal.