Software Engineering

# Convert Array to Tree in Java

## The challenge#

You are given a non-null array of integers. Implement the method arrayToTree which creates a binary tree from its values in accordance to their order, while creating nodes by depth from left to right.

For example, given the array [17, 0, -4, 3, 15] you should create the following tree:

``````    17
/  \
0   -4
/ \
3   15
``````

The class TreeNode is available for you:

``````class TreeNode {

TreeNode left;
TreeNode right;
int value;

TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}

TreeNode(int value) {
this(value, null, null);
}

@Override
public boolean equals(Object other) {
... // Already implemented for you and used in test cases
}
...
}
``````

## The solution in Java code#

Option 1:

``````public class Solution {

static TreeNode arrayToTree(int[] array) {
return arrayToTree(array, 0);
}
static TreeNode arrayToTree(int[] array, int index) {
return index < array.length ?
new TreeNode(array[index], arrayToTree(array, index * 2 + 1), arrayToTree(array, index * 2 + 2)) :
null;
}
}
``````

Option 2:

``````public class Solution {
static TreeNode arrayToTree(int[] values) {
return arrayToTree(values, 0);
}

static TreeNode arrayToTree(int[] values, int i) {
if (i >= values.length) return null;
return new TreeNode(values[i], arrayToTree(values, 2 * i + 1),
arrayToTree(values, 2 * i + 2));
}
}
``````

Option 3:

``````public class Solution {

static TreeNode arrayToTree(int[] array) {
if (array == null || array.length == 0) {
return null;
}
return arrayToTree(array, 0);
}

private static TreeNode arrayToTree(int[] array, int root) {
if (root >= array.length) {
return null;
}
return new TreeNode(
array[root],
arrayToTree(array, (root * 2) + 1),
arrayToTree(array, (root * 2) + 2)
);
}
}
``````

## Test cases to validate our solution#

``````import org.junit.Test;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.assertThat;

public class SolutionTest {

@Test
public void emptyArray() {
TreeNode expected = null;
assertThat(Solution.arrayToTree(arrayFrom()), is(expected));
}

@Test
public void arrayWithMultipleElements() {
TreeNode expected = new TreeNode(17, new TreeNode(0, new TreeNode(3), new TreeNode(15)), new TreeNode(-4));
assertThat(Solution.arrayToTree(arrayFrom(17, 0, -4, 3, 15)), is(expected));
}

private int[] arrayFrom(int... values) {
return values;
}
}
``````