Tree

Key:

1. Always draw the recursion tree

2. Recursive rule: because for each node, the value being returned to it and property of its children subtrees are the same, it's easy to set up the recursive rule

3. Base case (in general): null pointer under the leaf node

4. Knowing how traversal of a binary tree works. For each node, solve problems on its left child tree and right child tree will most likely solve the problem for the root(original tree)

Basic methods of thinking:

1. What do you expect from the left child and right child? Usually the return type of the recursive function

2. What do you do in the current layer of the recursion tree?

3. What do you report to the parent?