Trees

Tree problems are about choosing the right traversal and knowing what information each node must return to its parent. DFS is natural for subtree answers, BFS is natural for level-order answers, and BST problems add ordering constraints that let you discard branches.

Quick Identifier

• Topic: trees
• Pattern: DFS, BFS, BST invariant, path tracking, or tree DP.
• Core Question: What should each node compute locally, and what must be returned upward?

Quick Sights

• Typical Time Complexity: O(n) for one traversal, with some complete-tree/BST variants at O(log^2 n) or O(h).
• Typical Space Complexity: O(h) recursion stack for DFS, O(w) queue for BFS.
• Core Mechanism: Visit nodes in an order that makes the required child, parent, or level information available at the right time.

Diagram

Recognition Cues

• Height, diameter, balance, path sum, serialize, or subtree comparison.
• "Level order", "right side view", or "next pointer".
• BST, kth smallest, valid bounds, or inorder ordering.

Problem List

Start with 104. Maximum Depth, 226. Invert Binary Tree, 102. Level Order Traversal, 098. Validate BST, and 124. Binary Tree Maximum Path Sum.