Binary Search Tree to inOrder Array

Question

Pretty easy question:

Recursively how can I create an array of a binary search tree (in order) which uses this constructor:

public class OrderedSet<E extends Comparable<E>> {
    private class TreeNode {
    private E data;
    private TreeNode left, right;

    public TreeNode(E el) {
        data = el;
        left = null;
        right = null;
    }
}

  private TreeNode root;
  public int size = 0;

  public OrderedSet() {
    root = null;
  }

Solution 1

In-Order means you first have to traverse the left part of the tree, so:

TreeNode tree  // this is your tree you want to traverse
E[] array = new E[tree.size];  // the arrays length must be equivalent to the number of Nodes in the tree
int index = 0; // when adding something to the array we need an index
inOrder(tree, array, index);  // thats the call for the method you'll create

The method itself could looks something like this:

public void inOrder(TreeNode node, E[] array, int index){
    if(node == null){  // recursion anchor: when the node is null an empty leaf was reached (doesn't matter if it is left or right, just end the method call
       return;
    }
    inOrder(node.getLeft(), array, index);   // first do every left child tree
    array[index++]= node.getData();          // then write the data in the array
    inOrder(node.getRight(), array, index);  // do the same with the right child
}

Somewhat like that. I am just not sure about the index and where it needs to be incremented. If you don't want to worry about the index or if you don't know how many nodes are in the tree, then use an ArrayList instead and transform it in the end to an array.

Normally a cleaner call method is build around the recursive method like this:

public E[] inOrderSort(TreeNode tree){
    E[] array = new E[tree.size];
    inOrder(tree, array, 0);
    return array;
}

Solution 2

Thanks, that worked great. Java wouldn't allow me to make an array of generics so using your algorithm I made it work with an ArrayList (like you suggested) Here's the method (using the above constructor) just incase someone else asks the same question. (Ref is my reference to the current tree node)

public ArrayList<E> toArray() {
    ArrayList<E> result = new ArrayList<E>();
    toArrayHelp(root, result);
    return result;
}

private void toArrayHelp(TreeNode ref, ArrayList<E> result) {
    if (ref == null) {
        return;
    }
    toArrayHelp(ref.left, result); 
    result.add(ref.data); 
    toArrayHelp(ref.right, result); 
}