Find Sum of All Left Leaf Nodes of Binary Tree

  • Write a C program to find the sum of all left leaf nodes of a given binary tree.
  • Write a recursive function in C to find all leaf nodes sum.

Given a binary tree, we have to find the sum of all leaf nodes of binary tree. We have to traverse each node of binary tree and check whether current node is a left leaf node or not. A node is left leaf node if, current node is left child of it's parent and left and right child pointer of current node is NULL.

Algorithm to find sum of all left leaf nodes in binary tree.
  • Traverse given binary tree using pre order traversal.
  • Check if current node is a left leaf node. A node of binary tree is a leaf node if :
    1. If current node is left child of parent.
    2. If left and right child pointers of current node are NULL.
  • If current node is left leaf node, then add it's value to variable sum.
  • If current node is not a left leaf node then recursively calculate the sum of left leaf nodes in left and right sub tree and return.
Time Complexity : O(n)

C program to find sum of all leaf leaf nodes

#include <stdio.h>
#include <limits.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 tree
            1
           / \
         2    3
        / \    \
       4  5    6
      / \
     7  8
*/
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->right = getNewNode(6);
 
    root->left->left->left = getNewNode(7);
    root->left->left->right = getNewNode(8);
    
    return root;
}

int isLeafNode(struct node *nodePtr){
 if(nodePtr == NULL)
    return 0;
 else if (nodePtr->left == NULL && nodePtr->right == NULL)
    return 1;
 else 
    return 0;
}
/* This function calculates sum of all left leaf 
nodes in a binary tree */
int getleftLeafsSum(struct node *root) {

    int sum = 0;
    if (root != NULL) {
       /*Check if left node of root is a leaf node */
       if (isLeafNode(root->left)) {
           /* Add left leaf node data to sum */
        sum += root->left->data;
       } else {
           /* Recursively find sum of all left leaf 
     nodes in left sub tree */
           sum += getleftLeafsSum(root->left);
       }
 
        /* Recursively find sum of all left leaf 
   nodes in left sub tree */
        sum += getleftLeafsSum(root->right);
    }
    /* Sum sum of all left leaf node in a
  tree whose root node is root */
    return sum;
}

int main() {
    struct node *root = generateBTree();    
    
 printf("Left Leaf Sum : %d",getleftLeafsSum(root));
    
    getchar();
    return 0; 
}
Output
Left Leaf Sum : 7
Posted by
Labels: