Tree DFS
Explore tree paths using recursion (or explicit stack). Three traversal orders: pre-, in-, post-order. Great for path sums and BST validation.
Time
O(n)
Space
O(h) where h = height
Recognize it when
- Root-to-leaf path sums
- Max/min depth
- Validate BST properties
- All paths from root to leaf
Questions — ordered by difficulty
Path Sum
Determine if the tree has a root-to-leaf path that sums to target.
Path Sum II
Return all root-to-leaf paths where the path sum equals target.
Maximum Depth of Binary Tree
Find the maximum depth (number of nodes along the longest path from root to a leaf).
Diameter of Binary Tree
Find the length of the longest path between any two nodes in the tree (the diameter).
Validate Binary Search Tree
Determine if a binary tree is a valid BST.
Binary Tree Maximum Path Sum
Find the maximum path sum where the path can start and end at any node.
Lowest Common Ancestor of BST
Find the lowest common ancestor (LCA) of two nodes p and q in a BST. The LCA is the lowest node that has both p and q as descendants.
Lowest Common Ancestor of Binary Tree
Find the LCA of two nodes p and q in a general binary tree (not necessarily a BST).
Kth Smallest Element in a BST
Find the kth smallest element in a BST.
Serialize and Deserialize Binary Tree
Design an algorithm to serialize a binary tree to a string and deserialize it back to the original tree.
Recover Binary Search Tree
Two nodes in a BST are swapped by mistake. Recover the tree without changing its structure.