Balanced Binary Tree
EasyThe problem
A tree is balanced if, for every node, the heights of its left and right subtrees differ by at most 1. Return true if the whole tree is balanced, otherwise false.
- Example 1Input: root = [3, 9, 20, null, null, 15, 7]Output: true
- Example 2Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]Output: false
The left child of the root has height 3, but the right child has height 1, a gap of 2.
Limits
- 0 ≤ number of nodes ≤ 5,000
- An empty tree is balanced
- Height = number of nodes on the longest downward path
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Compute height and check balance in the same pass instead of recomputing heights.
The idea
DFS returns the height, or −1 as a signal that a subtree is unbalanced; propagate −1 upward.
Target: O(n) time
Go function shape
func isBalanced(root *TreeNode) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsBalanced: compute height and check balance in the same pass. A height of -1 means "already unbalanced",
// and it is passed up so nothing above recomputes anything.
func IsBalanced(root *TreeNode) bool {
var height func(*TreeNode) int
height = func(n *TreeNode) int {
if n == nil {
return 0
}
l, r := height(n.Left), height(n.Right)
if l == -1 || r == -1 || abs(l-r) > 1 {
return -1
}
return 1 + max(l, r)
}
return height(root) != -1
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}