1.9.3 Application

• Maximum Path Sum in a Binary Tree.
  For each node there can be four ways that the max path goes through the node: 
  1. Node only 
  2. Max path through Left Child + Node 
  3. Max path through Right Child + Node 
  4. Max path through Left Child + Node + Max path through Right Child 
   
  The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. In below code, this sum is stored in ’max_single’ and returned by the recursive function.

  Idea: (recursive + return style)

• in order without recursive,
  // An iterative process to print preorder traversal of Binary tree 
  void iterativePreorder(node *root){ 
      // Base Case 
      if (root == NULL) 
         return; 
   
      // Create an empty stack and push root to it 
      stack<node *> nodeStack; 
      nodeStack.push(root); 
   
      /* Pop all items one by one. Do following for every popped item 
         a) print it 
         b) push its right child 
         c) push its left child 
      Note that right child is pushed first so that left is processed first */ 
      while (nodeStack.empty() == false)    { 
          // Pop the top item from stack and print it 
          struct node *node = nodeStack.top(); 
          printf ("%d␣", node->data); 
          nodeStack.pop(); 
   
          // Push right and left children of the popped node to stack 
          if (node->right) 
              nodeStack.push(node->right); 
          if (node->left) 
              nodeStack.push(node->left); 
      } 
  }

  Idea: A common implementation of DFS, without check two unvisited condition. Because tree is a 1) minimally connected graph and having only one path between any two vertices. 2) no loop

• For search tree, look for lowest common ancestor(LCA).
  Node *LCA(Node *root, Node *p, Node *q) { 
    if (!root || !p || !q) return NULL; 
    if (max(p->data, q->data) < root->data) 
      return LCA(root->left, p, q); 
    else if (min(p->data, q->data) > root->data) 
      return LCA(root->right, p, q); 
    else 
      return root; 
  }
• Find a LCA in any tree.
  Method 1 (By Storing root to n1 and root to n2 paths): 
  Following is simple O(n) algorithm to find LCA of n1 and n2. 
  1) Find path from root to n1 and store it in a vector or array. 
  2) Find path from root to n2 and store it in another vector or array. 
  3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
• If target is present in tree, then prints all the ancestors and returns true, otherwise returns false.
                1  
              /   \  
            2      3  
          /  \  
        4     5  
       /  
      7  
   key is 7, then your function should print 4, 2 and 1.
  bool printAncestors(struct node *root, int target){ 
    /* base cases */ 
    if (root == NULL) 
       return false; 
    if (root->data == target) 
       return true; 
   
    /* If target is present in either left or right subtree of this node, 
       then print this node */ 
    if ( printAncestors(root->left, target) || 
         printAncestors(root->right, target) ){ 
      cout << root->data << "␣"; 
      return true; 
    } 
    /* Else return false */ 
    return false; 
  }

  Idea: just like max height example, return bool instead value, logic || instead max. the basic idea are quite same.