Given a binary tree write a c program to find maximum sum from root to leaf in a binary tree. For example if given binary tree is as below

In the above binary tree the maximum sum from root to leaf is 19 ( 6->5->8). Let us write  c program and learn how it works.

c program to find maximum sum from root to leaf in a binary tree

#include<stdio.h>
#include<malloc.h>

// data structure for binary tree
struct Tree
{
  int value;
  struct Tree *left;
  struct Tree *right;
};

struct Tree *root = NULL;

struct Tree *
makeNewNode (int value)
{
  struct Tree *node = (struct Tree *) malloc (sizeof (struct Tree));
  node->value = value;
  node->left = NULL;
  node->right = NULL;

  return node;
}

// function to find max sum

int maxSumFromRootToLeaf (struct Tree *root)
{
  // base case
  if (root == NULL)
    return 0;

  int l = maxSumFromRootToLeaf (root->left);
  int r = maxSumFromRootToLeaf (root->right);

  if (l > r)
    return l + root->value;
  else
    return r + root->value;
}

int main ()
{
  /*
     (6)
     /\
    /  \
   (8)  (5)
        / \
       /   \
     (8)  (3)

   */

  root = makeNewNode (6);
  root->left = makeNewNode (8);
  root->right = makeNewNode (5);

  root->right->left = makeNewNode (8);
  root->right->right = makeNewNode (3);


  root->right->left->left = NULL;
  root->right->left->right = NULL;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  int sum = maxSumFromRootToLeaf (root);
  printf ("The max sum from root to leaf is %d \n", sum);

  return 0;
}

How it works:

  • Traverse the binary tree from bottom up.
  • Calculate the max sum from node to leaf for left child.
  • Calculate the max sum from node to leaf for right child.

Time Complexity : O (n)



Related Contents to follow