\n1. The base case: this is the hardest to define. we need to figure out the boundury condition and return type \n2. the recursion rules: the return type should be the same as base case, some time we need to keep an eye on whether it is a pre-order, post-order or in-order traversal.\n3. write some easy example to run through. It is fine if the first two step are wrong, write some cases to figure which part is wrong.

\n1. The base case: this is the hardest to define. we need to figure out the boundury condition and return type \n2. the recursion rules: the return type should