A binary tree is balanced when, at every node, the heights of the left and right subtrees differ by at most 1. Return whether the tree is balanced.
DSA Animator › DSA Revision › Tree › Balanced Binary Tree
Remember: return the height, and use minus 1 as an error signal. Bottom up turns O of n squared into O of n. The video solves Balanced Binary Tree (LeetCode 110, Easy) with the DFS Height with Early Exit pattern from the Tree topic, and you can replay every step in the interactive Balanced Binary Tree animation.
A binary tree is balanced when, at every node, the heights of the left and right subtrees differ by at most 1. Return whether the tree is balanced.
The tree 3, 9, 20, 15, 7 is balanced, because every node passes the check. A chain like 1, 2, 3, 4 going down one side is not balanced.
You could compute the height of both subtrees at every node, from scratch. That repeats the same height work again and again, which is O of n squared on a chain. Instead, compute heights bottom up, just once.
Write a height function that also checks the balance as it goes. It returns the real height when the subtree is balanced. It returns minus 1 as a signal when it finds any imbalance. Once a child returns minus 1, pass minus 1 straight up without more work. The tree is balanced if the root does not return minus 1.
Leaves 9, 15 and 7 return height 1. At 20, both children have height 1, the difference is 0, so 20 returns 2. At the root, the left height is 1 and the right height is 2. The difference is 1, which is allowed, so the root returns 3. No minus 1 appeared, so the tree is balanced. On the chain 1, 2, 3, 4, node 2 would see heights 2 and 0, return minus 1, and the answer would be false.
In code, the helper returns 0 for null. It gets the left height, and returns minus 1 immediately if that is minus 1, and the same for the right. If the absolute difference is more than 1, it returns minus 1, otherwise 1 plus the larger height. Each node is visited once, so it's O of n time.
Remember: return the height, and use minus 1 as an error signal. Bottom up turns O of n squared into O of n.