Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Isn't a sorted array already a balanced heap. If parent = index i, then left child= 2*1+1, right child =2*i+2. Just traverse array in this this order and populate your BST.
public static Node ConvertToTree(int[] input, int lowerIndex, int higherIndex)
{
if (lowerIndex < higherIndex)
{
var mid = (higherIndex - lowerIndex) / 2 + lowerIndex;
var n = new Node(input[mid]);
n.left = ConvertToTree(input, lowerIndex, mid);
n.right = ConvertToTree(input, mid + 1, higherIndex);
return n;
}
return null;
}
I am building the tree from bottom up, and it is non-recursive.
If N = 2^m then the algorithm runs in O(1) space and returns a perfectly balanced tree with "N" elements.
If N = 2^m + k, then the algorithm runs in O(1) space, but first build a tree that might have "m" extra nodes. Then these nodes will be removed.
public class Node {
public Node left, right, parent;
public int key;
public Node(Node parent) {
this.parent = parent;
}
}
public Node getRoot(int[] sorted_array) {
// Assuming sort is ascending
int N = sorted_array.length;
int count = 0;
int max_h = (int) (Math.log(N) / Math.log(2));
int h = max_h;
Node root = new Node(null);
Node node = root;
// In O(log(N)) time, get the left most
while(count < N) {
if (node.left == null && h == 0) {
node.key = sorted_array[count++];
node = node.parent;
h++;
}
else if (node.left == null) {
node.left = new Node(node);
node = node.left;
h--;
}
else if (node.left != null && node.right == null) {
node.key = sorted_array[count++];
node.right = new Node(node);
node = node.right;
h--;
}
else {
node = node.parent;
h++;
}
}
while (node != root) {
node = node.parent;
if (node.key == 0) {
node.parent.left = node.left;
node.left.parent = node.parent;
}
}
return root;
}
Take the median of the array as the root of the tree. For sake of clarity let's call it original_median. Now , take the median of the array to the left of the original_median and make it the left child and similarly the median of the array to the right of the original_median and make it the right child. Recursively apply it to the left child and right child.
In C++:
- uuuouou March 05, 2014