How do I implement a method that returns an inorder sorted array in a java binary search tree?

Question

This is what I tried:

public int[] sortedArray() {
    int[] array = new int[size()];
    int index = 0;
    traverseInorder(root, array, index);
    return array;
}

private void traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        traverseInorder(n.left, array, index);
        array[index++] = n.value;
        traverseInorder(n.right, array, index);
    }
}

But the output is not correct.

If I create a tree with this input:

{1,5,8,10,12,15,20,22,25,36,30,40,28,38,48,45,50}

The output I get with sortedArray is this:

[1, 5, 8, 10, 12, 15, 20, 22, 25, 36, 40, 48, 50, 0, 0, 0, 0]

What did I do wrong? I realize that it skips all the left subtrees on the right side from the root, but I just can't see why...

Answer 1

You are overwriting all the left sub-trees elements written to the array.

Assuming you added the nodes to the tree in the specified order, you'll get the following (extremely unbalanced) tree:

   1
    \
     5
      \
       8
        \
         10
          \
           12
            \
             15
               \
                20
                 \
                  22
                   \
                    25
                     \
                     36
                    /  \
                   30   40
                  /    /  \
                 28   38   48
                          /  \
                         45   50

You can see that the 4 elements missing from the in-order output (28, 30, 38 & 45) all belong to left sub-trees.

The reason for that behavior is that after traverseInorder(n.left, array, index); writes the left sub-tree to the array and returns, any changes that it made to index are local, so array[index++] = n.value; and traverseInorder(n.right, array, index) overwrite the values of the left sub-tree previously written to the array.

To fix this, your recursive method should return the updated index:

private int traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        index = traverseInorder(n.left, array, index);
        array[index++] = n.value;
        index = traverseInorder(n.right, array, index);
    }
    return index;
}