Solve Tree Problems Recursively
- "Top-down" Solution
- "Bottom-up" Solution
Conclusion
In previous sections, we have introduced how to solve tree traversal problem recursively. Recursion is one of the most powerful and frequent used methods for solving tree related problems.
As we know, a tree can be defined recursively as a node(the root node), which includes a value and a list of references to other nodes. Recursion is one of the nature features of a tree. Therefore, many tree problems can be solved recursively. For each recursion level, we can only focus on the problem within one single node and call the function recursively to solve its children.
Typically, we can solve a tree problem recursively from the top down or from the bottom up.
"Top-down" Solution
"Top-down" means that in each recursion level, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively. So the "top-down" solution can be considered as kind of preorder traversal. To be specific, the recursion function top_down(root, params) works like this: 1
2
3
4
5
61. return specific value for null node
2. update the answer if needed // anwer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
For instance, consider this problem: given a binary tree, find its maximum depth.
1 | 1. return if root is null |
"Bottom-up" Solution
"Bottom-up" is another recursion solution. In each recursion level, we will firstly call the functions recursively for all the children nodes and then come up with the answer according to the return values and the value of the root node itself. This process can be regarded as kind of postorder traversal. Typically, a "bottom-up" recursion function bottom_up(root) will be like this: 1
2
3
41. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
If we know the maximum depth l of the subtree rooted at its left child and the maximum depth r of the subtree rooted at its right child, can we answer the previous question? Of course yes, we can choose the maximum between them and plus 1 to get the maximum depth of the subtree rooted at the selected node. That is x = max(l, r) + 1.
It means that for each node, we can get the answer after solving the problem of its children. Therefore, we can solve this problem using a "bottom-up" solution. Here is the pseudocode for the recursion function maximum_depth(root): 1
2
3
41. return 0 if root is null // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1 // return depth of the subtree rooted at root