## IBM Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

Suppose we need to build a balanced binary search tree T for the elements in sorted array A, from index "lo" to "hi".

```
build(A, lo, hi):
The root of T must be the middle element: T.root = A[mid], where mid = (lo+hi)/2
The left subtree of T must be built from A[lo, mid), recursively:
T.left = build(A, lo, mid-1)
The right subtree of T must be built from A[mid+1, hi), recursively:
T.right = build(A, mid+1, hi)
```

Remember the basecase is when hi-lo <=1.

Complexity:

Since each element of the array A is accessed once, the complexity is O(N), N = length of array A.

The iterative solution -

```
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public static TreeNode buildTreeIterative(int[] nums) {
Stack<int[]> pos = new Stack<>();
Stack<TreeNode> nodes = new Stack<>();
TreeNode root = new TreeNode(-1);
pos.push(new int[] {0, nums.length - 1});
nodes.push(root);
while(!nodes.isEmpty()) {
// Get the current node
TreeNode node = nodes.pop();
// Pop an element from the stack
int[] range = pos.pop();
int start = range[0];
int end = range[1];
int mid = range[0] + (range[1] - range[0])/2;
node.val = nums[mid];
if(start < mid) {
// There exists a left child for the node
node.left = new TreeNode(-1);
pos.push(new int[] {start, mid - 1});
nodes.push(node.left);
}
if(end > mid) {
// There exists a right child for the node
node.right = new TreeNode(-1);
pos.push(new int[] {mid + 1, end});
nodes.push(node.right);
}
}
return root;
}
```

TreeNode* BuildMinimalTreeFromArr(int* arr , int left, int right){

if(left > right){

return NULL;

}

else{

int mid = (left+right)/2;

TreeNode* root = new TreeNode;

root->data = arr[mid];

root->left = BuildMinimalTreeFromArr(arr,left,mid-1);

root->right = BuildMinimalTreeFromArr(arr,mid+1,right);

return root;

}

}

Building balanced BST from sorted array (Swift):

```
class Node {
var data: Int
var left: Node?
var right: Node?
init(data: Int, left: Node?, right: Node?) {
self.data = data
self.left = left
self.right = right
}
}
var arr = [1,2,3,4,5,6,7,8,9]
func buildTree(arr: [Int]) -> Node? {
if arr.count == 0 {
return nil
}
var mid = arr.count / 2
var left : Node? = nil
if mid > 0 {
left = buildTree(Array(arr[0..<mid]))
}
var right : Node? = nil
if mid < arr.count - 1 {
right = buildTree(Array(arr[mid+1..<arr.count]))
}
let node = Node(data: arr[mid], left: left, right: right)
return node
}
var root = buildTree(arr)
```

- Yash Katariya January 18, 2016