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
0 Comments
Inline Feedbacks
View all comments