BST Traversal Patterns

Combine search decisions with traversals: range queries prune whole subtrees when bounds make them 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 is the speed-up—do not visit irrelevant children.
• Same pattern extends to count, average, or reporting nodes.
• Know when input is guaranteed BST vs general binary tree.