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

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

1. Pick traversal based on the information needed.
2. For BST, use inorder or low/high bounds.
3. For path sums, return one-side extendable path and update global best with a fork.
4. 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

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.