[Java/all] Maximum Level Sum in a tree?

Since there isn't really any code posted with this, I can't really verify much of anything. That said, For example if you have this tree:

           20
        /      \
      /          \
    10           40
   / \             \
  3   15            89
 /
1

And you want to find the maximum level in the tree from a specific node (in this case just an integer), you could probably do it in a few ways. I'll just show the way to do it recursively for now.

int maxLevel(BinaryTree node) {
    // 1. Base case -> node does not exist in tree, so we return -1
    if (node == null) {
        return -1;
    }

   // 2. Decomposition -> we are calling our method on both the left
   //    and right sub-trees and storing the result.
   int leftLevel   = maxLevel(node.getLeft());
   int rightLevel  = maxLevel(node.getRight());

   // 3. Solving the original problem ->  We are checking to see which
   //    sub-tree has a higher level so far and then adding the current 
   //    level to it.
   if(leftLevel > rightLevel) {
       return leftLevel + 1;
   } else {
       return rightLevel + 1;
   }
}

To better visualize this, here is what the method adds when we call maxLevel(root) where root holds the value 20 from our tree above. The format is maxLevel(data in node) and max([maxLevel(node1)], maxLevel(node2)) signifies the check that returns the current maximum level between two nodes. The [] around a node shows the node that will be returned from max(...).

                          maxLevel(20) = max([maxLevel(10)], maxLevel(40)) + 1
                                       = [2] + 1
                                     /             \
                                  /                   \ 
                               /                         \
                             /                               \
                           /                                      \
                        maxLevel(10)                            maxLevel(40)
          = max([maxLevel(3)],maxLevel(15)) + 1               = max(maxLevel(null), [maxLevel(89)]) + 1
          = [1] + 1                                           = [0] + 1
               /      \                                                \
            /               \                                              \
         /                       \                                              \
      /                                 \                                             \
   /                                           \                                            \
maxLevel(3)                                  maxLevel(15)                                maxLevel(89)
= max([maxLevel(1)], maxLevel(null)) + 1     = [return -1] + 1                        = [return -1] + 1
= [0] + 1                                    = [-1] + 1                               = [-1] + 1
     /
   /
maxLevel(1)
= [return -1] + 1
= [-1] + 1

Going from the code, maxLevel(20) ends up searching through each subtree looking for the maximum level. If it happens upon a node with no children, we return -1 + 1 which is 0. We then go up the tree returning the maximum of each value we requested.

There are also iterative approaches to this problem which can be found online. But hopefully the recursive approach helps you understand the problem better.

/r/learnprogramming Thread