Trees & Recursion
Tree DFS · Inorder
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
inorderBSTsorted orderkth smallestvalidate BSTin-order successor
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Is it a BST and you want values in sorted order?
- kth-smallest, validate-BST, in-order successor?
- Recurse in order: left, then visit, then right.
Classic problem
Binary Tree Inorder Traversal — Visit left subtree, then root, then right: left → root → right. For a BST, inorder produces a sorted sequence.
Input: Binary tree with nodes A(root), B(left), C(right), D(B-left), E(B-right), F(C-left), G(C-right)
Output: [D, B, E, A, F, C, G] — left subtrees visited before each root.
Common pitfalls
Forgetting the null base case.
Assuming sorted output on a tree that isn’t a BST — the ordering only holds there.