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.

Traverse with intent (not vibes)

Order	Pattern	Computes when
Preorder	node → left → right	path snapshots, clones, serializers that write root first
Inorder	left → node → right	BST sorted order
Postorder	left → right → node	subtree aggregates (“delete children before parent”, diameter pieces)
Level-order (BFS)	queues by depth	widths, ladders, ZigZag layering

Whenever you recurse, articulate the tuple returned upward (“height”, “validated min/max subtree sum”, etc.). If you cannot phrase it as a capsule of child answers joined at the current node, the recursion is fuzzy.

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

Loading 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.