DFS on Trees
Prereq: DFS Introduction
Think like a node
The key to solving tree problems using DFS is to think from the perspective of a node instead of looking at the whole tree. This is in line with how recursion is written. Reason from a node, make sure you consider all the cases and let recursion takes care of the rest. Provided you have a good understanding of the problem at hand, there are two things you want to think about:
1. Return value
What do we want to return after visiting a node. For example, for max depth problem this is max depth for the current node's subtree. If we are looking for a node in the tree, we'd want to return that node if found, else return null. Use return value to pass information from children to parent.
2. Identify states
What states do we need to maintain to compute the return value for the current node. For example, to know if the current node's value is larger than its parent we have to maintain the parent's value as a state. State becomes DFS's function arguments. Use states to pass information from parent to children.
The template for DFS on tree is:
def dfs(root, state): if not root: ... return left = dfs(root.left, state) right = dfs(root.right, state) ... return ...
This may sound abstract at the moment. Let's do a couple of concrete problems.