Balanced BST — log height

Balance — height log; AVL/red-black implementations.

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

• Bottom-up (ok, height).
• AVL vs red-black strictness.
• B-tree — block storage.