Inorder on a BST — Sorted Order

For a valid BST, inorder visits keys in sorted order. Many problems reduce to “simulate sorted array” on the implicit sequence.

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 inorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# BST example
r = TreeNode(2, TreeNode(1), TreeNode(3))
print(inorder(r))

Key takeaways

• Inorder successor/predecessor ideas power iterator designs.
• kth smallest often uses stack simulation of inorder.
• Validate BST by carrying allowed min/max windows.