Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Thanks for replying. May I know what is the Big O of the following solutoin for same problem and why?
public boolean isBalanaced(Node root){
if(root == null) return true;
int heightDiff = getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff > 1)){
return false;
}else{
return isBalanced(root.left) && isBalanced(root.right);
}
}
private int getHeight(Node root){
if(root == null) return 0;
else{
return Math.max(getHeight(root.left) + getHeight(root.right)) + 1;
}
I'd have given a different algorithm. The recursion you've shown is clumsy and has a lot more code than needed.
The rule for balance: |# of levels on left - # of levels on right| <= 1
We only need two methods, the starting method, and the recursion. I'll be using java here.
public boolean isBalanced(Node root){
int left = balance_check(root.left);
int right = balance_check(root.right);
return (Math.pow(left - right, 2) <= 1);
}
public int balance_check(Node root){
if(root == null) return 0;
return 1 + (Math.max(balance_check(root.left), balance_check(root.right));
}
The first function simply calls the recursion to create a left and right value, then compares the square of their difference (which will always be positive) to 1 and returns the boolean of the equation.
The recursion will return 0 is it is given a non-existent node. Otherwise, it will give back 1 + the largest value found recursively of its two children. At the bottom level, a leaf node will have 0 left, 0 right, and thus return only a value of 1. The node above that, assuming both its children are leaf nodes, will return 2. The node above that, which let's say has 2 from the left and 3 from the right, will return 4, etc etc. This way we have the maximum depth of each side. Dynamic programming would put this equation as
OPT(x) = { 1 if x is a leaf,
1 + max(OPT(x.left), OPT(x.right)) if x is internal
}
It will run in O(N) time, since each node will be visited only once by the above layers.
Get leaf node at max depth and get leaf node at minimum depth, if difference is greater than 1 then tree is not balanced.
Inorder/preorder/postorder any of the 3 traversal can be modified to get maxdepth and mindepth.
below is the code for maxdepth similary min depth can be found.
ms-amazon.blogspot.co.uk/2012/08/calculate-depth-of-binary-tree.html
complexity : O(n)
Every node is visited exactly twice. Once while going down and the other time while the calls are being returned. That is why the time complexity is O(N).
- Hingle McCringleBerry October 04, 2013In general if the number of times an algorithm visits the tree node is upper bounded by some constant "k", then the running time is O(N).
For further practice, try to solve problem no 12.2-7 in the CLRS book(3rd edtn)