Prashant Kr. -3 years ago 76
Java Question

Convert tree to its preOrder Array (recursively)

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) {
System.out.println("enter root ");
int data = in.nextInt();
if (data == -1)                // no root is formed
return null;
BinaryTreeNode<Integer> root = new BinaryTreeNode<>(data);

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;
}

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;
}
}
return root;
}
``````

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

``````public static void print_Binary_Tree_LEVEL_WISE(BinaryTreeNode<Integer> 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) {
print += "L:" + currentRoot.left.data + ",";
} else {
print += "L:" + -1 + ",";
}
if (currentRoot.right != null) {
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.

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;