## IBM Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 6 vote

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;
int end = range;
int mid = range + (range - range)/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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.