DFS on Trees
Go as deep as possible before coming back, usually with recursion.
0 of 4 problems solved
DFS on Trees
Go as deep as possible before coming back, usually with recursion.
- •Am I supposed to go as deep as possible before returning?
- •Would recursion naturally process left and right children?
- •Do I know what each recursive call should return?
Depth First Search on trees means you follow one path as far as it goes before you come back. Recursion is a natural match because each node can ask the same question of its left child and right child. For max depth, you ask, 'How deep is my left side? How deep is my right side?' Then the current node adds one for itself.
Trees get easier when every node solves the same small subproblem for its children.
- 1Handle the base case: an empty node contributes zero depth.
- 2Recursively compute the left depth and right depth.
- 3Take the larger one.
- 4Add one for the current node.
Forgetting the base case for null nodes makes recursion crash or return the wrong depth.
Construct Binary Tree from Preorder and Inorder Traversal
The first element of preorder is always the root. Locate it in inorder to split left and right subtree sizes. Recurse with matching slices.
Binary Tree Maximum Path Sum
Post-order DFS. leftGain = max(0, dfs(left)), same for right. Update global max with node + leftGain + rightGain. Return only the larger single-branch gain up.