IBM Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
from binaryTree import BinaryTree
def arrayBST(l,start,end):
mid=(start+end)/2
if start<=end:
tree=BinaryTree(l[mid])
tree.left=arrayBST(l,start,mid-1)
tree.right=arrayBST(l,mid+1,end)
return tree
def inorder(tree):
if tree!=None:
inorder(tree.left)
print tree.key
inorder(tree.right)
def preorder(tree):
if tree!=None:
print tree.key
preorder(tree.left)
preorder(tree.right)
t=arrayBST([1,2,3,4],0,3)
inorder(t)
print
preorder(t)
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.
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)
The iterative solution -
- anshul.chandra October 07, 2017