# Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height

I'm trying to find the complexity of this code and some suggestions for improving the code quality. and handling the code gracefully, esp in the areas of exception handling, checking edge cases, presentation, etc.

// Node Class

class Node {
int id;
Node left;
Node right;
Node(int id) {
this.id = id;
left = null;
right = null;
}
}


// ArrayIntoBinaryTree Class

import java.util.Scanner;
public class ArrayIntoBinaryTree {

/*
Algorithm:
1. Insert into the tree the middle element of the array.
2. Insert (into the left subtree) the left subarray elements
3. Insert (into the right subtree) the right subarray elements
4. Recurse
*/

ArrayIntoBinaryTree arrayIntoBinaryTree = new ArrayIntoBinaryTree();

public static void main(String[] args) {
int[] arr = initializeArray();
if (arr == null) {
throw new NullPointerException("Input array is empty");
}
Node node = addToTree(arr, 0, arr.length);
}

// find Subarray - Use Recursion.
static Node addToTree(int[] arr, int first, int last) {
// Exit condition
if(first<last) {
return null;
}
int midElement = arr[(first+last)/2];
Node newNode = new Node(arr[midElement]);
return newNode;
}

static int[] initializeArray() {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of array: ");
int size = sc.nextInt();

if (size < 1) {
return null;
}

System.out.println("Now enter " + size + " number of elements.");
int[] arr = new int[size];
for(int i=0; i<size; i++) {
arr[i] = sc.nextInt();
}
return arr;
}
}


Bug 1

if(first<last) {
return null;
}


This is wrong. It will return a null for the very root of the tree. Change to

if (last - first < 1) {
return null;
}


Bug 2

int midElement = arr[(first+last)/2];
Node newNode = new Node(arr[midElement]);


This is wrong too. You should have instead:

int middleIndex = (first + last) / 2;
Node newNode = new Node(arr[middleIndex]);
newNode.right = addToTree(arr, middleIndex + 1, last);


if(first<last) {
...
}


According to Java coding conventions, you must have a single space after if and before an opening (. Also, each binary operator must have a single space before and after it. Putting things together, you must write

if (first < last) {
...
}


I suggest you move the tree node to its own file and declare it non-public. Also, I suggest you roll a public tree type that can validate that data is traversed in-order in the same order as the elements in the input array.

Alternative implementation

IntBinaryTreeNode.java

final class IntBinaryTreeNode {

private int datum;
private IntBinaryTreeNode leftChild;
private IntBinaryTreeNode rightChild;

IntBinaryTreeNode(int datum) {
this.datum = datum;
}

int getDatum() {
return datum;
}

IntBinaryTreeNode getLeftChild() {
return leftChild;
}

IntBinaryTreeNode getRightChild() {
return rightChild;
}

void setLeftChild(IntBinaryTreeNode leftChild) {
this.leftChild = leftChild;
}

void setRightChild(IntBinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}


IntBinaryTree.java

import java.util.function.Consumer;

/**
* Implements a simple binary tree in which each node contains an integer. This
* implementation does not enforce any order so it is not a binary search tree.
*/
public class IntBinaryTree {

private final IntBinaryTreeNode root;

IntBinaryTree(IntBinaryTreeNode root) {
this.root = root;
}

public void inOrderTraversal(Consumer<Integer> consumer) {
inOrderTraversal(root, consumer);
}

private void inOrderTraversal(IntBinaryTreeNode node,
Consumer<Integer> consumer) {
if (node == null) {
return;
}

inOrderTraversal(node.getLeftChild(), consumer);
consumer.accept(node.getDatum());
inOrderTraversal(node.getRightChild(), consumer);
}
}


IntArrayToBinaryTreeConverter.java

    public final class IntArrayToBinaryConverter {

public IntBinaryTree convert(int[] array) {
IntBinaryTreeNode root = convert(array, 0, array.length);
return new IntBinaryTree(root);
}

/**
* Converts a range {@code array[fromIndex], ..., array[toIndex - 1]} into
* a binary search tree.
*
* @param array     the array of integers to convert into nodes.
* @param fromIndex the starting, inclusive index of the range to convert.
* @param toIndex   the ending, exclusive index of the range to convert.
* @return
*/
private IntBinaryTreeNode convert(int[] array,
int fromIndex,
int toIndex) {
int rangeLength = toIndex - fromIndex;

if (rangeLength < 1) {
return null;
}

int middleIndex = fromIndex + ((toIndex - fromIndex) >>> 1);
IntBinaryTreeNode node =
new IntBinaryTreeNode(array[middleIndex]);
node.setLeftChild(convert(array, fromIndex, middleIndex));
node.setRightChild(convert(array, middleIndex + 1, toIndex));
return node;
}
}


Main.java

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the array length: ");
int arrayLength = scanner.nextInt();
System.out.print("Enter all the array components: ");
int[] array = new int[arrayLength];

for (int i = 0; i < arrayLength; ++i) {
array[i] = scanner.nextInt();
}

IntBinaryTree tree =
new IntArrayToBinaryConverter().convert(array);

tree.inOrderTraversal(System.out::println);
}
}

• Thank you. This was really helpful. Regarding the complexity of my original code(+your suggestions), what would be the complexity? – user2769790 Jan 18 '18 at 19:33
• @user2769790 It's $\Theta(N)$. However, your (and mine) procedure will construct just a binary tree and not a binary search tree. If you need a binary search tree, sort the array prior to passing to the tree building method; that will take $\Theta(N \log N)$ time in the worst case. – coderodde Jan 18 '18 at 19:35