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