Tree DFS and BST Inorder Patterns

Learning Outcome

Use recursive return values, inorder sortedness, and tree-to-graph conversion for tree interview problems.

Pattern Recognition

Item	Detail
Core signal	The problem asks for subtree values, path values, BST order, distance from target, or level-based properties.
Use when	Each node answer depends on left/right subtree answers or BFS levels.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

Define exactly what a recursive call returns upward; keep global answers separate when paths can bend.

Exact Practice Question Names

Binary Tree Inorder Traversal
Validate Binary Search Tree
Kth Smallest Element in a BST
Binary Tree Maximum Path Sum
Amount of Time for Binary Tree to Be Infected
Maximum Width of Binary Tree

Interview Approach

Pick traversal based on the information needed.
For BST, use inorder or low/high bounds.
For path sums, return one-side extendable path and update global best with a fork.
For burning/distance, add parent links or build an undirected graph.

Pseudocode

dfs(node):
  if node is null: return base
  left = dfs(node.left)
  right = dfs(node.right)
  update answer using node, left, right
  return value parent needs

Sample Dry Run

In max path sum, a node may combine left + node + right for the global answer, but it can return only node plus one side to its parent.

Edge Cases

Empty tree
Single node
Negative values
BST values equal to int min/max

Common Mistakes

Returning a forked path upward
Using int bounds for BST validation
Forgetting parent direction in burn tree problems

Complexity

Item	Detail
Expected time	Usually O(n).
Expected space	O(h) recursion or O(n) for BFS/parent maps.

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.