C Program to Check Root to Leaf Path Sum Equal to a Given Number

• Write a C program to check if there exist a path from root to leaf whose sum is N.

Given a binary tree and a number N, we have to check if binary tree has a path from root node to any leaf node whose sum is equal to N. We will traverse every node of binary tree using pre order traversal and keep track of the sum of nodes in current path. Whenever we reach a leaf node, we will check whether path sum is equal to N. If yes then there exist a path from root to leaf node whose sum is N.

---

Algorithm to check root to leaf path equals N
Let "node" be the pointer to any node during pre order traversal.

• If node is equal to NULL and path sum is not equal to N then return false.
• If node is equal to NULL, then check whether path sum is equal to N or not. If yes then return true else return false.
• Recursively traverse left and right sub tree by passing path sum as sum + node->data. Now node will be part of all paths to any leaf node of sub tree rooted at node.

Time Complexity : O(n)

---

C program check root to leaf path sum equals N

#include <stdio.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below 
            1
           / \
         2    3
        / \  / \
       4  5 6  7
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
    
    return root;
}

/*
It checks that whether a path exists from nodePtr to any of 
the leaf nodes whose sum is equal to the given number 
*/
int rootToLeafPathSum(struct node* nodePtr, int sum, int N) {
  
  if(nodePtr == NULL)
      return 0;
      
  /* If leaf node data is equal to sum then we found a 
  path from root to leaf */
  if (nodePtr->left == NULL && nodePtr->right == NULL) {
     if(nodePtr->data + sum == N) 
         return 1;
     else 
         return 0;
  }
  /* Check recursively on sub-tree or right sub-tree */ 
  return rootToLeafPathSum(nodePtr->left, sum + nodePtr->data, N) || 
      rootToLeafPathSum(nodePtr->right, sum + nodePtr->data, N);
}

int main() {
    struct node *root = generateBTree();    
    
    if(rootToLeafPathSum(root, 0, 8)){
        printf("There exist a path from root to a leaf node\n");
    } else {
        printf("No such path exists\n");
    }
    
    getchar();
    return 0; 
}

Output

There exist a path from root to a leaf node