any simple reasoning that why changing
if not tree: return 0 to return None can still pass a few test case but not all?
Can the logic be simply like?
So, in each node we can recurse and return 1 (current node) + abs(left node height - right node height)
Finally, at the root node, height is less than or equal one if tree is balanced.
function isBalanced(tree) {
const dfs = (node) => {
if (!node) return 0;
return 1 + Math.abs(dfs(node.left) - dfs(node.right));
};
return dfs(tree) <= 1;
}
Are you sure it will compile?
You have to check balanced at each node(subtree).
I think there’s issue with Math.abs(dfs(node.left) - dfs(node.right))
It’d fail cases like this: https://i.imgur.com/zkguhyC.png
We don’t have this edge case yet, will add it.
I enter this custom test data “1 2 3 4 5 x x 8 9 x x x x x x”, which I believe is the tree you mentioned, and it passed the test!
Could you please confirm the data represents the edge case tree?
added the case 1 2 3 4 x x 4 x x 3 x x 2 x x
Thanks for adding the edge case, now I can see it!
It’s always good to have more tests and cover edge cases, to be sure the solution works properly.
Does Test #3 look like this?
1
2 5
3 4
6
If that is a correct picture, then it seems to me the answer should be ‘True’, so I am asking for some clarification, thanks !!
Are we sure example 2 is unbalanced? If I am incorrect and it is, I am not so sure why?
I also don’t understand why example 2 is unbalanced
I think it’s because node 3 is unbalanced because there’s no left node (height = 0) and its right node has a height of 2.
The subtrees of the node labelled 3 has a height difference of 2 (left is 0, right is 2), so it is not balanced.
def is_balanced(tree: Node) → bool:
def max_height(node):
if not node:
return 0
else:
return max(max_height(node.left), max_height(node.right)) + 1
if not tree:
return True
else:
left = max_height(tree.left)
right = max_height(tree.right)
return abs(left - right) <= 1 and is_balanced(tree.left) and is_balanced(tree.right)
where’s js solution
adblock plus has blocked your images
can you explain this
if left_height is -1 or right_height is -1:
return -1
if abs(left_height - right_height) > 1:
return -1
I avoid using nonlocal variables but I really think it simplified the solution. It may dock you if the interviewer wants you to not have “global” within your Python function, but I think it’s really easy to follow/derive incase you get stuck and to have something working and explained clearly.
def is_balanced(tree: Node) → bool:
# PostOrder DFS
# We need height of left and right subtrees and find abs diff
# Then say if its <= 1 → true, else false
# If node = none → true
# We need height vals → so return int or pass that state
# down so we can keep the function at bool and avoid a global
is_balanced = True
def dfs(node: Node) -> int:
nonlocal is_balanced
if not node:
return 0
L = dfs(node.left)
R = dfs(node.right)
if abs(L - R) > 1:
is_balanced = False
return max(L, R) + 1
dfs(tree)
return is_balanced
Yes! This took me a while to understand. So -1 here is just a flag to return false (but instead the function returns int not bool). This is because as soon as we find a subtree that is unbalanced, we want to end the search and return -1 for every stack frame. This will continue popping off every frame on the stack until -1 is returned as the final answer —> indicating that the tree is unbalanced.
Do you really need lines 13 and 14 in the solution? If you remove them, all of the tests still pass. Either they aren’t necessary or another test case needs to be added to show why it is needed.