← all entries
A-049● Day 492026.06.24easyleetcode #110neetcode150

Balanced Binary Tree

#tree#depth-first-search#binary-tree
↗ leetcode #110 · balanced-binary-tree
01

Problem

· problem
P.049

Balanced Binary Tree

↗ leetcode #110

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the absolute difference between the heights of the left and right subtrees of every node is at most 1.

constraints
  • · The number of nodes in the tree is in the range [0, 5000].
  • · -10⁴ ≤ Node.val ≤ 10⁴
// paraphrased summary — see source for full text
examples
example 1input → output
[3,9,20,null,null,15,7]
true
example 2input → output
[1,2,2,3,3,null,null,4,4]
false
example 3input → output
[]
true
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What does height-balanced mean?
  • ☐
    Is an empty tree height-balanced?
  • ☐
    Is a single node height-balanced?
  • ☐
    If all subtrees are balanced, is the whole tree balanced?
  • ☐
    Do we need to recalculate heights multiple times?
  • ☐
    Is a complete binary tree always height-balanced?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Base case: Check for null node│ nested
○
if not root:
○
if not root.left and not root.right:
○
if root == None:
step 2· Base case: Return [balanced, height]│ nested
○
return [True, 0]
○
return [True, 1]
○
return (True, 0)
step 3· Recursive calls: Explore both subtrees│ nested
○
left, right = dfs(root.left), dfs(root.right)
○
left, right = dfs(root.right), dfs(root.left)
○
if dfs(root.left) and dfs(root.right):
step 4· Validate balance: Check three conditions│ nested
○
balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
○
balanced = abs(left[1] - right[1]) <= 1
○
balanced = left[0] and right[0] and abs(left[1] - right[1]) < 1
step 5· Return current node: [balanced, updated height]│ nested
○
return [balanced, 1 + max(left[1], right[1])]
○
return [balanced, 1 + left[1] + right[1]]
○
return [balanced, max(left[1], right[1])]
step 6· Final return: Extract root's balance status
○
return dfs(root)[0]
○
return dfs(root)[1]
○
return dfs(root)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
9
        def dfs(root):
10
            if not root:
11
                return [True, 0]
12
13
            left, right = dfs(root.left), dfs(root.right)
14
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
15
            return [balanced, 1 + max(left[1], right[1])]
16
17
        return dfs(root)[0]
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[3,9,20,null,null,15,7]
→
true
case 2
[1,2,2,3,3,null,null,4,4]
→
false
case 3
[]
→
true
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.