Convert tree to its preOrder Array (recursively)

Question

I am trying to convert the tree to its preorder array eg if a tree is like:

         1
       /    \
    2       3                                         ________
then its preOrder array should be   | 1 | 2 | 3 |
                                                        - - - - - - - -

Here are some tree inputs:

//  2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1
//  10 9 4 -1 -1 5 8 -1 6 -1 -1 3 -1 -1 -1
//  1 2 9 3 4 -1 10 5 -1 -1 5 -1 -1 -1 -1 -1 6 -1 7 -1 8 -1 -1
//  1 2 6 3 7 -1 -1 4 -1 -1 8 5 -1 -1 9 -1 -1 -1 10 -1 -1
//  1 2 3 -1 -1 -1 -1

Code in my Main.java :

public class Main {
    public static void main(String[] args) throws QueueEmptyException {
        Scanner in = new Scanner(System.in);

        BinaryTreeNode<Integer> root = BinaryTreeNode.takeInput_LEVEL_WISE(in);        // tree input taken
        BinaryTreeNode.print_Binary_Tree_LEVEL_WISE(root);

        // create its preOrder array
        int pre[] = BinaryTreeNode.preOrder_Array(root);
        for (int val : pre) {
            System.out.print(val + " ");
        }

        // create its postOrder array
    }
}

Here is my Tree Node:

public class BinaryTreeNode<T> {
    public T data;
    public BinaryTreeNode<T> left;
    public BinaryTreeNode<T> right;

    BinaryTreeNode(T data) {
        this.data = data;
        left = null;
        right = null;
    }
}

The take input Method: (No problem in this)

public static BinaryTreeNode<Integer> takeInput_LEVEL_WISE(Scanner in) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        System.out.println("enter root ");
        int data = in.nextInt();
        if (data == -1)                // no root is formed
            return null;
        BinaryTreeNode<Integer> root = new BinaryTreeNode<>(data);
        q.add(root);

        int left, right;
        while (!q.isEmpty()) {
            BinaryTreeNode<Integer> currentRoot = q.poll();
            System.out.println("enter left of " + currentRoot.data + " :  ");
            left = in.nextInt();

            if (left == -1) {
                currentRoot.left = null;
            } else {
                BinaryTreeNode<Integer> leftChild = new BinaryTreeNode<>(left);
                currentRoot.left = leftChild;
                q.add(leftChild);
            }


            System.out.println("enter right of " + currentRoot.data + " :  ");
            right = in.nextInt();
            if (right == -1) {
                currentRoot.right = null;
            } else {
                BinaryTreeNode<Integer> rightChild = new BinaryTreeNode<>(right);
                currentRoot.right = rightChild;
                q.add(rightChild);
            }
        }
        return root;
    }

Code for the print function: (No problem in this too)

public static void print_Binary_Tree_LEVEL_WISE(BinaryTreeNode<Integer> root) {
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        q.add(root);

        String print = "";
        while (q.size() != 0) {        // until not empty
            BinaryTreeNode<Integer> currentRoot = q.poll();
            print = currentRoot.data + ":";

            // adding the right and left
            if (currentRoot.left != null) {
                q.add(currentRoot.left);
                print += "L:" + currentRoot.left.data + ",";
            } else {
                print += "L:" + -1 + ",";
            }
            if (currentRoot.right != null) {
                q.add(currentRoot.right);
                print += "R:" + currentRoot.right.data;
            } else {
                print += "R:" + -1;
            }

            System.out.println(print);
        }
    }

---

Here is the code for PreOrder array: (Facing problem in this)

    public static int[] preOrder_Array(BinaryTreeNode<Integer> root) {
        if (root == null)
            return new int[0];        // array of 0 size

        int n = noOfNodesIN_Tree(root);
        int pre[] = new int[n];

        preOrder_Array_Helper(pre, root, 0);
        return pre;
    }

    private static void preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) {
        if (root == null)
            return;        //-> base case

        pre[index] = root.data;
//      index++;
        if (index == pre.length) {
            return;
        } else {        // call for recursion
            preOrder_Array_Helper(pre, root.left, index + 1);
            preOrder_Array_Helper(pre, root.right, index + 1);
        }
    }

I understand the problem, it's due to the indexes in recursion (the values keeps on overriding at the same location/index), but I have no idea how to solve this problem, how do i make the indexes increment.

This could be done easily by the arrayList but I want to do it with arrays.

Answer 1

You can return last updated index as result of method and use it in recursive call:

private static int preOrder_Array_Helper(int[] pre, BinaryTreeNode<Integer> root, int index) {
    if (root == null)
        return index;        //return the same as get

    pre[index] = root.data;
    index++; 
    if (index == pre.length) {
        return index;  //return new value after add
    } else {  
        index = preOrder_Array_Helper(pre, root.left, index);  //get last after left branch visit
        return preOrder_Array_Helper(pre, root.right, index); //use new index in right branch
    }
}

or you can use List<Integer> to avoid all this problems with index managing:

public static List<Integer> preOrder_Array(BinaryTreeNode<Integer> root) {
    if (root == null)
        return new ArrayList<>();        // array of 0 size

    List<Integer> pre = new ArrayList<>();

    preOrder_Array_Helper(pre, root);
    return pre;
}

private static void preOrder_Array_Helper(List<Integer> pre, BinaryTreeNode<Integer> root) {
    if (root == null)
        return;

    pre.add(root.data);
    preOrder_Array_Helper(pre, root.left);
    preOrder_Array_Helper(pre, root.right);

}