Given a binary tree, find the sum of all the leaf nodes.
Examples:
Input : 1 / 2 3 / / 4 5 6 7 8 Output : Sum = 4 + 5 + 8 + 7 = 24
The idea is to traverse the tree in any fashion and check if the node is the leaf node or not. If the node is the leaf node, add node data to sum variable.
Following is the implementation of above approach.
C++
// CPP program to find sum of // all leaf nodes of binary tree #include<bits/stdc++.h> using namespace std; // struct binary tree node struct Node{ int data; Node *left, *right; }; // return new node Node *newNode( int data){ Node *temp = new Node(); temp->data = data; temp->left = temp->right = NULL; } // utility function which calculates // sum of all leaf nodes void leafSum(Node *root, int *sum){ if (!root) return ; // add root data to sum if // root is a leaf node if (!root->left && !root->right) *sum += root->data; // propagate recursively in left // and right subtree leafSum(root->left, sum); leafSum(root->right, sum); } // driver program int main(){ //contruct binary tree Node *root = newNode(1); root->left = newNode(2); root->left->left = newNode(4); root->left->right = newNode(5); root->right = newNode(3); root->right->right = newNode(7); root->right->left = newNode(6); root->right->left->right = newNode(8); // variable to store sum of leaf nodes int sum = 0; leafSum(root, &sum); cout << sum << endl; return 0; } |
Java
// Java program to find sum of // all leaf nodes of binary tree public class GFG { // user define class node static class Node{ int data; Node left, right; // constructor Node( int data){ this .data = data; left = null ; right = null ; } } static int sum; // utility function which calculates // sum of all leaf nodes static void leafSum(Node root){ if (root == null ) return ; // add root data to sum if // root is a leaf node if (root.left == null && root.right == null ) sum += root.data; // propagate recursively in left // and right subtree leafSum(root.left); leafSum(root.right); } // driver program public static void main(String args[]) { //contruct binary tree Node root = new Node( 1 ); root.left = new Node( 2 ); root.left.left = new Node( 4 ); root.left.right = new Node( 5 ); root.right = new Node( 3 ); root.right.right = new Node( 7 ); root.right.left = new Node( 6 ); root.right.left.right = new Node( 8 ); // variable to store sum of leaf nodes sum = 0 ; leafSum(root); System.out.println(sum); } } // This code is contributed by Sumit Ghosh |
Python3
# Python3 Program to find the #sum of leaf nodes of a binary tree # Class for node creation class Node: # Constructor def __init__( self , data): self .data = data self .left = None self .right = None # Utility function to calculate # the sum of all leaf nodes def leafSum(root): global total if root is None : return if (root.left is None and root.right is None ): total + = root.data leafSum(root.left) leafSum(root.right) # Binary tree Fromation if __name__ = = '__main__' : root = Node( 1 ) root.left = Node( 2 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right = Node( 3 ) root.right.right = Node( 7 ) root.right.left = Node( 6 ) root.right.left.right = Node( 8 ) # Variable to store the sum of leaf nodes total = 0 leafSum(root) # Printing the calculated sum print (total) # This code is contributed by Naren Sai Krishna |
C#
using System; // C# program to find sum of // all leaf nodes of binary tree public class GFG { // user define class node public class Node { public int data; public Node left, right; // constructor public Node( int data) { this .data = data; left = null ; right = null ; } } public static int sum; // utility function which calculates // sum of all leaf nodes public static void leafSum(Node root) { if (root == null ) { return ; } // add root data to sum if // root is a leaf node if (root.left == null && root.right == null ) { sum += root.data; } // propagate recursively in left // and right subtree leafSum(root.left); leafSum(root.right); } // driver program public static void Main( string [] args) { //contruct binary tree Node root = new Node(1); root.left = new Node(2); root.left.left = new Node(4); root.left.right = new Node(5); root.right = new Node(3); root.right.right = new Node(7); root.right.left = new Node(6); root.right.left.right = new Node(8); // variable to store sum of leaf nodes sum = 0; leafSum(root); Console.WriteLine(sum); } } // This code is contributed by Shrikant13 |
Output:
24
Time Complexity : O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments