IBM Interview Question
AccountantsCountry: United States
int maxDepth(node* root)
{
if(NULL == root)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}
int minDepth(node* root)
{
if(NULL == root)
return 0;
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}
int isBalanced(node* root)
{
if(maxDepth(root) - minDepth(root) > 1)
return 0;
else
return 1;
}
Will this still be a correct solution.
public static int maxDepth(TreeNode root){
if(root == null){
return 0;
}
return 1+ Math.max(maxDepth(root.left), maxDepth(root.right));
}
public static boolean isBalanced(TreeNode root){
return (maxDepth(root.left) - minDepth(root.right) <= 1);
}
Why do we find MinDepth. Please explain.
int checkBalance(Node n, Boolean flag) {
if(n == null) return -1;
int leftHeight = checkBalance(n.left) + 1;
int rightHeight = checkBalance(n.right) + 1;
if(Math.Abs(leftHeight - rightHeight) > 1) flag = true;
return max(leftHeight, rightHeight);
}
bool isBalance(Node n) {
Boolean flag = false;
checkBalance(n);
return flag;
}
Here is a neat code to check whether a tree is balanced or not,
- Anonymous January 22, 2012puddleofriddles.blogspot.com/search?q=balanced