Prashant Kr. 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) {
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 Source

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

}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download