## JP Morgan Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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));
}

//Worked Well..

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
Node left;
Node right;
int data;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isBalance=true;

int isBalanceTree(Node n){
if(n==null) return 0;
int hl=isBalance(n.left);
int hr=isBalance(n.right);
if(Math.mod(hl,hr)>1 && isBalance)
isBalance=false;
return 1+Max(hl,hr);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.