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;
    }
}
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments