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 } ... }
Code language: Java (java)

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; } }
Code language: Java (java)

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)); } }
Code language: Java (java)

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) ); } }
Code language: Java (java)

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; } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
1 Comment
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
Mikehenry
Mikehenry
29 days ago

I’ve been looking for this solution, thank you.
FYI, you site is quite clean and descriptions very clear.