BST traversal patterns

Range query — prune subtree when bounds impossible.

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 range_sum(root: TreeNode | None, lo: int, hi: int) -> int:
    if not root:
        return 0
    if root.val < lo:
        return range_sum(root.right, lo, hi)
    if root.val > hi:
        return range_sum(root.left, lo, hi)
    return root.val + range_sum(root.left, lo, hi) + range_sum(root.right, lo, hi)

r = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, None, TreeNode(18)))
print(range_sum(r, 6, 14))

Key takeaways

• Pruning — speed.
• Count/report variants.
• BST vs general tree.