I think the solution doing via post order was confused. Instead, I came up with a pre order solution:
public static boolean isBalanced(Node<Integer> tree) {
return dfs(tree) <= 1;
}
private static int dfs(Node<Integer> node) {
if (node == null) return -1;
if (node.left == null && node.right == null) return 1;
int left = dfs(node.left);
int right = dfs(node.right);
return Math.abs(left + right);
}
Just a question here - wouldnât it make more sense to get the left subtree height, check if the left subtree is balanced, get the right subtree height, and then check if the right subtree is balanced? It seems to me that you potentially save some work if you determine that the left subtree is unbalanced first, then you would never even have to check the right subtree. It does make the recursive function a couple lines longer, but was just curious if that makes sense. So instead of:
nt leftHeight = treeHeight(tree.left);
int rightHeight = treeHeight(tree.right);
if (leftHeight == -1 || rightHeight == -1) {
return -1;
}
if would be:
// Get the left subtree height
int leftHeight = dfs(node.left);
// If leftHeight returns as -1, this is our flag that our left
// subtreee is not balanced
if (leftHeight == -1) {
return leftHeight;
}
// Get the right subtree height
int rightHeight = dfs(node.right);
// If rightHeight returns as -1, this is our flag that our right
// subtreee is not balanced
if (rightHeight == -1) {
return rightHeight;
}
It would be nice if they explained what âheight differenceâ is.
why is the solution so convolutedâŚ
class Solution {
private:
int maxHeight(TreeNode* root) {
if (!root)
return 0;
int left = maxHeight(root -> left) + 1;
int right = maxHeight(root -> right) + 1;
return std::max(left, right);
}
public:
bool isBalanced(TreeNode* root) {
if(!root)
return true;
int lstree = maxHeight(root â left);
int rstree = maxHeight(root â right);
if(std::abs(lstree - rstree) > 1)
return false;
bool left = isBalanced(root -> left);
bool right = isBalanced(root -> right);
return left && right;
}
};
oops im stupid this is O(n^2)
is if left_height is -1 or right_height is -1:
return -1
needed? Tests pass without it
Yes because as soon as you find the unbalanced node you can stop traversing the tree. Without it you will pass through an unbalanced node.
1 2 2 3 x x 3 4 x x 4
Try this one
How come Test #2 and Test #5 are supposed to be imbalanced?
Test #2: 1 2 4 x 7 x x 5 x x 3 x 6 8 x x x == >(left:3 , right: 3)
|1|
|2| |3|
|4| |5| |6|
|7| |8|
Test #5: 1 2 3 x x 4 x x 5 6 x 7 x x x (left:2, right: 3)
Hi Shaimaa,
This confused me too. It turns out all subtrees have to be balanced in order for the tree to be balanced. (I think this was unclear in the overview since they only say âboth its subtreeâ, and not all its subtrees.)
As you point out, the left and right subtrees of the root node do have heights within 1 level of each other. However, each has a subtree that is out of balance. For example, in test #2, the subtree 3 x 6 8 x x x is out of balance.
Hope this helps!
Thanks for posting. I just noticed I made the same mistake.
I see, thanks for the clarification Joe
My weird solution using tuple
def is_balanced(tree: Node) -> bool:
# WRITE YOUR BRILLIANT CODE HERE
def getHeight(node):
if node is None:
return (0, True)
leftH, leftValid = getHeight(node.left)
rightH, rightValid = getHeight(node.right)
valid = abs(leftH - rightH) < 2
return (1 + max(leftH, rightH), leftValid and rightValid and valid)
return getHeight(tree)[1]
JS Structured Programming Solution:
function isBalanced(tree) {
return getDepth(tree) !== -1;
}
function getDepth(node) {
let result = 0;
if (node != null) {
const left = getDepth(node.left);
const right = getDepth(node.right);
result = left === -1 || right === -1 || Math.abs(left - right) > 1
? -1
: Math.max(left, right) + 1;
}
return result;
}
Same as below but properly formatted
function isBalanced(tree) {
return getDepth(tree) !== -1;
}
function getDepth(node) {
let result = 0;
if (node != null) {
const left = getDepth(node.left);
const right = getDepth(node.right);
result = left === -1 || right === -1 || Math.abs(left - right) > 1
? -1
: Math.max(left, right) + 1;
}
return result;
}
Similar solution and more readable
public static int height(Node tree) {
if (tree == null) return 0;
// decide on what to return when visiting this node
// we want to return the height of the tree.
// height of the tree is the largest number of edges from the root to that tree
int lhsHeight = height(tree.left) + 1;
int rhsHeight = height(tree.right) + 1;
return Math.max(lhsHeight, rhsHeight);
}
public static boolean isBalanced(Node<Integer> tree) {
// WRITE YOUR BRILLIANT CODE HERE
if (tree == null) {
return true;
}
int lhsHeight = height(tree.left);
int rhsHeight = height(tree.right);
boolean lhsBalanced = isBalanced(tree.left);
boolean rhsBalanced = isBalanced(tree.right);
if (Math.abs(lhsHeight - rhsHeight) <= 1) {
return lhsBalanced && rhsBalanced;
}
return false;
}
Java & C++ are F tier aka garbo for interviews
Stick to javascript and python bois
JS solution
function isBalanced(tree) {
// WRITE YOUR BRILLIANT CODE HERE
let balanced=true;
const dfs = (node) =>{
if(node===null) return 0;
const left = dfs(node.left);
const right = dfs(node.right);
if(Math.abs(left-right)>1) balanced=false;
return Math.max(left,right)+1
}
dfs(tree);
return balanced;
}
function isBalanced(tree) {
// WRITE YOUR BRILLIANT CODE HERE
let balanced=true;
const dfs = (node) =>{
if(node===null) return 0;
const left = dfs(node.left);
const right = dfs(node.right);
if(Math.abs(left-right)>1) balanced=false;
return Math.max(left,right)+1
}
dfs(tree);
return balanced;
}