Balanced BST — Keep Height Logarithmic

Balance keeps operations near O(log n) by bounding height. AVL and red–black trees are classic implementations; interviews often ask the height invariant idea first.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def height(n: TreeNode | None) -> int:
    return 0 if not n else 1 + max(height(n.left), height(n.right))


def is_balanced(root: TreeNode | None) -> bool:
    def dfs(n: TreeNode | None) -> tuple[bool, int]:
        if not n:
            return True, 0
        ok_l, h_l = dfs(n.left)
        ok_r, h_r = dfs(n.right)
        ok = ok_l and ok_r and abs(h_l - h_r) <= 1
        return ok, 1 + max(h_l, h_r)

    return dfs(root)[0]

r = TreeNode(1, TreeNode(2, TreeNode(3)), TreeNode(4))
print(is_balanced(r))

Key takeaways

• Check balance bottom-up with (ok, height) pairs to avoid repeated scans.
• AVL enforces stricter balance than typical red–black.
• B-trees optimize block storage—different cost model.