Tuesday 22 September 2015

Maximum sum along any path of binary tree of positive numbers

Problem


Given a binary tree where each node contains positive numbers, find the maximum sum that is possible along any path of the binary tree.

Solution


We will solve this recursively. The function f(node) will return the maximum sum of the tree rooted at the node. So f(node)=node.value+ max(f(node.left),f(node.right)). f(node.left) and f(node.right) will be calculated recursively. For f(null) we will return 0;

Code

public class MaxSumTreePathPositive
{
 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(6);
  Node g = new Node(7);
  Node h = new Node(8);
  a.left = b;
  a.right = c;
  b.left = d;
  c.left = e;
  c.right = f;
  f.left = g;
  f.right = h;
  int maxSum = findMaxSum(a);
  System.out.println(maxSum);
 }

 private static int findMaxSum(Node root)
 {
  if (root == null)
   return 0;
  return root.value
    + Math.max(findMaxSum(root.left), findMaxSum(root.right));
 }

 static class Node
 {
  Node left;
  Node right;
  int value;

  public Node(int value)
  {
   this.value = value;
  }
 }

}

   

No comments:

Post a Comment