Balanced Binary Tree
Recursion returns height — propagate a -1 sentinel up if any subtree is unbalanced.
3 min read
tree dfs recursion
Problem#
Return true iff a binary tree is height-balanced — for every node the heights of its two subtrees differ by at most 1.
Examples#
[3,9,20,null,null,15,7]→true.[1,2,2,3,3,null,null,4,4]→false.
Constraints#
0 <= nodes <= 5000.
Approach#
DFS returning height. If either subtree returns -1 (unbalanced) or their heights differ by more than 1, return -1. Otherwise return 1 + max(left, right).
Solution#
struct TreeNode { int val; TreeNode* left; TreeNode* right; };
class Solution { int height(TreeNode* n) { if (!n) return 0; int l = height(n->left); if (l < 0) return -1; int r = height(n->right); if (r < 0) return -1; if (abs(l - r) > 1) return -1; return 1 + max(l, r); }public: bool isBalanced(TreeNode* root) { return height(root) >= 0; }};func isBalanced(root *TreeNode) bool { var height func(*TreeNode) int height = func(n *TreeNode) int { if n == nil { return 0 } l := height(n.Left) if l < 0 { return -1 } r := height(n.Right) if r < 0 { return -1 } if l-r > 1 || r-l > 1 { return -1 } if l > r { return 1 + l } return 1 + r } return height(root) >= 0}from typing import Optional
class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def height(n: Optional[TreeNode]) -> int: if not n: return 0 l = height(n.left) if l < 0: return -1 r = height(n.right) if r < 0: return -1 if abs(l - r) > 1: return -1 return 1 + max(l, r)
return height(root) >= 0var isBalanced = function(root) { const height = (n) => { if (!n) return 0; const l = height(n.left); if (l < 0) return -1; const r = height(n.right); if (r < 0) return -1; if (Math.abs(l - r) > 1) return -1; return 1 + Math.max(l, r); }; return height(root) >= 0;};class Solution { private int height(TreeNode n) { if (n == null) return 0; int l = height(n.left); if (l < 0) return -1; int r = height(n.right); if (r < 0) return -1; if (Math.abs(l - r) > 1) return -1; return 1 + Math.max(l, r); }
public boolean isBalanced(TreeNode root) { return height(root) >= 0; }}function isBalanced(root: TreeNode | null): boolean { const height = (n: TreeNode | null): number => { if (!n) return 0; const l = height(n.left); if (l < 0) return -1; const r = height(n.right); if (r < 0) return -1; if (Math.abs(l - r) > 1) return -1; return 1 + Math.max(l, r); }; return height(root) >= 0;}Editorial#
The single-pass technique avoids the naive O(n^2) (recompute heights at every node). The -1 sentinel doubles as both “this is unbalanced” and “propagate the failure upward” — saves a separate boolean.
Complexity#
- Time:
O(n). - Space:
O(h)recursion.
Concept revision#
Related#