Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
private static int height(BSTNode n)
{
if (n==null)
return 0;
else return max(height(n.lChild),height(n.rChild))+1;
}
private static int max(int a , int b)
{
return (a>=b?a:b);
}
public boolean balanced()
{
int diff = Math.abs(height(root.left)-height(root.right));
if (diff >1)
return false;
else return true;
}
Just curious and pardon my ignorance. I have seen "WAP" in other questions. Why is it called WAP?
Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.
int height(Node root) {
if(root==null)
return 0;
else
return (max(height(root.left),height(root.right)) +1);
}
boolean balanced(Node root) {
int diff = Math.abs(height(root.left) - height(root.right));
if(root == null)
return true;
else {
if (root.left ==null && root.right == null)
return true;
else if (diff <=1 && balanced(root.left) && balanced(root.right))
return true;
else
return false;
}
}
Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.
int height(Node root) {
if(root==null)
return 0;
else
return (max(height(root.left),height(root.right)) +1);
}
boolean balanced(Node root) {
int diff = Math.abs(height(root.left) - height(root.right));
if(root == null)
return true;
else {
if (root.left ==null && root.right == null)
return true;
else if (diff <=1 && balanced(root.left) && balanced(root.right))
return true;
else
return false;
}
}
- Event Horizon December 26, 2013