BST Search — Walk the Inequality

Compare target with current value: go left if smaller, right if greater; None means absent.

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 search(root: TreeNode | None, x: int) -> bool:
    while root:
        if x == root.val:
            return True
        if x < root.val:
            root = root.left
        else:
            root = root.right
    return False

r = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7))
print(search(r, 4), search(r, 6))

Key takeaways

• Iterative BST search is tail-recursion in disguise.
• Average depth O(log n) if balanced; worst O(n) if skewed.
• Parent pointer variants need careful predecessor logic.