Here’s my solution:
def is_balanced(node: Node) → bool:
def dfs(node):
if not node:
# no height
return 0
sub_tree_height = max(dfs(node.left), dfs(node.right)) + 1 # plus one cuz of current node
if sub_tree_height > 1:
return False
return True
return dfs(node)
I focused on the definition: the tree is balanced by definition, and the height is the max height between the two subtrees plus 1. So if that assertion is false, then the tree is not balanced. What do you say?
My solution:
def is_balanced(tree: Node) → bool:
def dfs(node):
if node is None:
return 0
height_left = dfs(node.left)
height_right = dfs(node.right)
if abs(height_left - height_right) > 1:
return False
return 1 + max(height_left, height_right)
return dfs(tree)
Wouldn’t it be slightly more optimal here to check for -1 after find the height of the left subtree? That way if the left subtree returns -1, we can just return -1 immediately instead of checking the entirety of the right subtree.
I don’t understand why example 2 is false? It looks like it’s only off by 1.
I have this solution that passes all tests and it’s simpler than provided. Did I miss an edge case?
def is_balanced(tree: Node) → bool:
if tree is None:
return True
left_height = is_balanced(tree.left)
right_height = is_balanced(tree.right)
if abs(left_height - right_height) > 1:
return False
return max(left_height, right_height) + 1
Thank you , this cleared it up for me!
In what case the height will ever be = -1 ???
I agree, this would save work. I wonder if they don’t bother doing that improvement because it doesn’t impact the O(h) runtime and therefore doesn’t make it significantly more optimized. However, I’m curious if an small improvement like that be significant in an interview setting, and therefore worth putting in the final Java solution.
I had the same thought, and it’s obviously true - you should definitely short circuit the execution as soon as you reach your first unbalanced subtree. Calculating the right subtree’s height before assessing whether the left subtree is unbalanced is indeed premature.
I wonder if the reason they did it this way was just to illustrate fully the idea of the post-order traversal.
def is_balanced(tree: Node) -> bool:
def dfs(node):
if not node:
return -1, True
left_depth, is_left_balanced = dfs(node.left)
right_depth, is_right_balanced = dfs(node.right)
depth = max(left_depth, right_depth) + 1
is_bal = is_left_balanced and is_right_balanced and abs(left_depth - right_depth) <= 1
return depth, is_bal
_, is_bal = dfs(tree)
return is_bal
The code simply wont compile as it doesnt recognize the new function that I have written. what am i missing?. 
bool is_balanced(Node* tree) {
// WRITE YOUR BRILLIANT CODE HERE
if(tree == NULL)
{
return true;
}
return std::abs(tree_height(tree->left) - tree_height(tree->right)) <= 1;
}
int tree_height(Node* node)
{
if(node == NULL)
{
return 0;
}
return std::max(tree_height(node->right), tree_height(node->left)) + 1;
}
solution.cc: In function ‘bool is_balanced(Node*)’:
solution.cc:30:21: error: ‘tree_height’ was not declared in this scope
30 | return std::abs(tree_height(tree->left) - tree_height(tree->right)) <= 1;
We should check left_height == -1 and return -1 as soon as possible. Same applied to right_height. The solution code runs left_height, right_height, and then check if left_height == -1 or right_height == -1. We can just terminate as soon as we detect an unbalanced subtree.
What do you think about the below code, it worked for the tests, the logic is that if the current node doesnt satisfy the condition to be balanced, then it will return -1 like the solution by algomonster, but if that is the case, then no other logic is needed to determine the whole tree is unbalanced because that -1 will make the parent recursive calls also fail the balance condition and ultimately the first call to the root of the tree, hence not needing another validation (I know it’s horrible in terms of code maintenance, but it seems to work and that was the solution that I first thought, and it passed the tests, but not sure if there is an edge case which would fail)
def is_balanced(tree: Node) -> bool:
# WRITE YOUR BRILLIANT CODE HERE
def post_traverse(tree: Node)-> int:
if not tree:
return 0
#children_left = post_traverse
left = post_traverse(tree.left)
right = post_traverse(tree.right)
if abs(left - right) > 1:
return -1
result = max(left, right) + 1
return result
left = post_traverse(tree.left)
right = post_traverse(tree.right)
if (left - right) <= 1:
return True
return False
A couple of things:
1.) As mentioned previously it seems quicker to short circuit after doing the left side check if it’s already unbalanced. But I appreciate that this is emphasizing the pre order traversal approach for DFS.
2.) Actually tree_height returns tree height + 1 but this is fine for the calculation of tree balancing