# Objective

Given an array of distinct integers, use them to build a balanced binary search tree.

# Observations

1. The number of nodes in the left and right subtrees of a binary tree differ by at most 1.
2. Every node in the left subtree of a binary search tree is less than or equal to the value of the parent (root) node.
3. Every node in the right subtree of a binary search tree is greater than the value of the parent (root) node.
4. The root node of a balanced binary search tree is the middle value in the tree’s set of values.
5. The middle element of a sorted array corresponds to the root node of a binary search tree.
Code
``````import java.util.*;

/*
*	Given an array of distinct integers, use them to build a balanced binary search tree.
*/
class Solution {
/*
*	Node class for constructing a binary tree of integers.
*/
class Node {
private int data;
public Node left;
public Node right;

public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

/*
*	Build a binary search tree for a given range of indices. Called by {@link Solution#arrayToBalancedBST}.
*
*	@param int[] numbers An array of distinct integers sorted in ascending order.
*	@param int start The starting index for the smallest element in the BST.
*	@param int end The ending index for the largest element in the BST.
*
*	@return Node The root of the BST constructed from the given range of indices.
*/
private Node build(int[] numbers, int start, int end) {
System.err.println("Called build for range " + start + " to " + end);

Node root = null;

// If we can create at least one new node for the given range of indices
if (start <= end) {
// Get index of new parent/root node
int mid = (start + end) / 2;
root = new Node(numbers[mid]);
System.err.println("Created Node: " + root.data);

// This isn't super necessary but it saves 2 extra function
// calls for each leaf node that would return null
if (start != end) { // Comment this out to see the unnecessary calls
root.left = build(numbers, start, mid - 1);
root.right = build(numbers, mid + 1, end);
}
}

// Return the new root
return root;
}

/*
*	@return The root of a balanced binary search tree
*/
public Node arrayToBalancedBST(int[] numbers) {
// Sort numbers in ascending order
Arrays.sort(numbers);

return build(numbers, 0, numbers.length - 1);
}

/*
*	Prints an in-order tree traversal.
*/
public void inOrder(Node root) {
// Traverse all the way left
if (root.left != null) {
inOrder(root.left);
}

// Print current node
System.out.println("Traversed Node: " + root.data);

// Continue traversal with right subtree
if (root.right != null) {
inOrder(root.right);
}
}

/*
*	Driver function
*/
public static void run() {
Solution solution = new Solution();
int[] numbers = {5, 4, 7, 3, 2, 1, 6};
Node root = solution.arrayToBalancedBST(numbers);
solution.inOrder(root);
}

public static void main(String[] args) {
Solution.run();
}
}``````