JP Morgan Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
typedef struct tree{
int data;
struct tree *left;
struct tree *right;
}TREE;
TREE *root;
int max(int a, int b) {
return a > b ? a : b;
}
int depth(TREE *root){
if(root == NULL)
return 1;
return 1 + max(depth(root->left), depth(root->right));
}
int isBalanced(TREE *root) {
if(root == NULL)
return 1;
if(abs(depth(root->left) - depth(root->right)) > 1)
return 0;
return isBalanced(root->left) && isBalanced(root->right);
}
public static boolean checkBinaryTreeIsBalanced(BSTNode root){
if(computeAndCheckHeight(root) == -1)
return false;
else
return true;
}
public static int computeAndCheckHeight(BSTNode root){
if(root == null)
return 0;
int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
if(leftSubTreeHeight == -1)
return -1;
int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
if(rightSubTreeHeight == -1)
return -1;
int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
if(heightDifference > 1)
return -1;
else
return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
}
Time complexity : o(n)
public static boolean checkBinaryTreeIsBalanced(BSTNode root){
if(computeAndCheckHeight(root) == -1)
return false;
else
return true;
}
public static int computeAndCheckHeight(BSTNode root){
if(root == null)
return 0;
int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
if(leftSubTreeHeight == -1)
return -1;
int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
if(rightSubTreeHeight == -1)
return -1;
int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
if(heightDifference > 1)
return -1;
else
return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
}
public static boolean checkBinaryTreeIsBalanced(BSTNode root){
if(computeAndCheckHeight(root) == -1)
return false;
else
return true;
}
public static int computeAndCheckHeight(BSTNode root){
if(root == null)
return 0;
int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
if(leftSubTreeHeight == -1)
return -1;
int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
if(rightSubTreeHeight == -1)
return -1;
int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
if(heightDifference > 1)
return -1;
else
return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
}
time complexity : o(n)
I made a few assumptions regarding the definition and scope of the question:
1. I assume Balanced tree is referring to Height-balanced tree.
2. I take the following definition of Height balanced trees: A binary tree is height-balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
NOTE the part regarding inner nodes only.
struct node
{
int data;
node* left;
node* right;
};
int checkBalance(node* root) {
// base case
if(node == NULL) return 0;
int leftHeight = checkBalance(node->left);
int rightHeight = checkBalance(node->right);
// propogate error
if(leftHeight == -1 || rightHeight == -1)
return -1;
// give error on non-balance
if(abs(leftHeight - rightHeight) > 1)
return -1;
return max(leftHeight, rightHeight) + 1;
}
bool isHeightBalanced(node* root) {
if(checkBalance(root) == -1)
return false;
return true;
}
If either of the left or right subtrees is unbalanced, the entire tree becomes unbalanced. Hence the propogation of error through the entire depth of the recursive stack.
Bool isTreeBalanced(Node root){
if( !root.Left && !root.Right ){
Return true;
}
if( !root.Left || !root.Right){
if(getDepth(root.Left) > 1 || getDepth(root.Left) >1){
Return false;
}else{
Return true;
}
}
isTreeBalanced(root.Left == false){
Return false;
}
isTreeBalanced(root.Right == false){
Return false;
}
Return True;
}
Int getDepth(Node root){
if( !root.Left && !root.Right){
Return 0;
}
Else{
Int rightDepth = getDepth(root.Right);
Int leftDepth = getDepth(root.Left);
if(rightDepth > rightDepth){
Return rightDepth;
}else{
Return leftDepth;
}
}
}
- Jagadeesha Toohima March 09, 2016