1.9.2 Tree and recursion

Nearly all the tree problems can be resolved by recursive. When you recursive tree traversal, There are some points that you need to pay attention to:

1. Forgetting to check if the root is null. It’s an important base case.
2. Checking if one or both children are null. You SHOULD NOT do that. When you do the recursive call and pass the root.left() or the root.right() as the parameter, the recursive function will call itself and treating the passed child as the new root. So, you don’t need to explicitly check if the children are null.
3. Accessing the children values. You SHOULD NOT do that. The same as the previous point. The child passed to the recursive call is treated as the new root. So, you don’t need to explicitly access the children values. Just make sure you do that for the root.
4. If it is required from you to write a function that returns a value (e.g. the number of nodes in a binary tree), you have to make sure that the function actually "returns". One of the common mistakes is just writing the recursive call without writing the word "return" before it.
5. If you write a recursive tree that returns a value, the left and right branching should be done in an assignment statement, e.g.,
   private int height(Node t){ 
        if(t == null)  {  //1) base case 
           return -1;   //5) return value 
        } 
        else 
        { 
            int height = 1 + max( height(t.left), height(t.right) ); 
            //5) put left and right recursive into assignment 
            return height; 
        } 
   }
   private int countLeaves(Node t){ 
      if(t == null) 
            return 0; 
    
            if(isLeaf(t))  { 
                return 1; 
            } 
            else 
                return countLeaves(t.left) +countLeaves( t.right); 
        }
6. how many nodes are there in a tree.
   int BinaryTree::size(Node *leaf) const { 
       if(leaf == NULL) { //This node doesn’t exist. Therefore there are no nodes in this ’subtree’ 
           return 0; 
       } else { //Add the size of the left and right trees, then add 1 (which is the current node) 
           return size(leaf->getLeft()) + size(leaf->getRight()) + 1; 
       } 
   }
7. Information flow:
   1. return value from child to parent, (only return one value, so need some calculation inside from both left and right children)
   2. pass from parent to child, parameter to remember auto value(level) ,
   3. shared between children and parent. and pass a pointer parameter(max_level) to remember static, which all recursive
   // Recursive function to print left view of a binary tree. 
   void leftViewUtil(struct node *root, int level, int *max_level){ 
       // Base Case 
       if (root==NULL)  return; 
    
       // If this is the first node of its level 
       if (*max_level < level){ 
           printf("%d\t", root->data); 
           *max_level = level; 
       } 
    
       // Recur for left and right subtrees 
       leftViewUtil(root->left, level+1, max_level); 
       leftViewUtil(root->right, level+1, max_level); 
   }
8. recursive can be used to deal with two trees at the same time.
   int identicalTrees(struct node* a, struct node* b){ 
       /*1. both empty */ 
       if (a==NULL && b==NULL) 
           return 1; 
    
       /* 2. both non-empty -> compare them */ 
       if (a!=NULL && b!=NULL)    { 
           return( 
               a->data == b->data && 
               identicalTrees(a->left, b->left) && 
               identicalTrees(a->right, b->right) 
           ); 
       } 
    
       /* 3. one empty, one not -> false */ 
       return 0; 
   }

Conclusion:

1. According to question, if it will return a value, such as leaf count, height. It has to have a function.
2. Write base case
   if(root == nullptr) 
          return [value]
3. consider a node with two null children. that is the easiest tree. then finish the basic logic. At this time. value of function on left and right children have been known by the previous base case
   // If this is calculate how many nodes. 
   if(root == nullptr) 
          return 0; 
        return 1+ recursive(root->left) + recursive(root-right); 
        //so a node tree, nodeNum(root->left) return 0. 
    
        cout<<node<<endl; 
        recursive(root->left); 
        recursive(root->right); 
        //or print a node.  such as pre-order, in-order, post-order traversal.
4. For some easy problems, you have finished the problems. Then for some difficult problems, you need to some logic comparison or calculation. such as Maximum path sum in a binary tree. or max height tree.