Given a Binary Tree, find sum of all left leaves in it. For example, sum of all left leaves in below Binary Tree is 5+1=6.
The idea is to traverse the tree, starting from root. For every node, check if its left subtree is a leaf. If it is, then add it to the result.
Following is the implementation of above idea.
C++
// A C++ program to find sum of all left leaves #include <iostream> using namespace std; /* A binary tree Node has key, pointer to left and right children */ struct Node { int key; struct Node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointer. */ Node *newNode( char k) { Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } // A utility function to check if a given node is leaf or not bool isLeaf(Node *node) { if (node == NULL) return false ; if (node->left == NULL && node->right == NULL) return true ; return false ; } // This function returns sum of all left leaves in a given // binary tree int leftLeavesSum(Node *root) { // Initialize result int res = 0; // Update result if root is not NULL if (root != NULL) { // If left of root is NULL, then add key of // left child if (isLeaf(root->left)) res += root->left->key; else // Else recur for left child of root res += leftLeavesSum(root->left); // Recur for right child of root and update res res += leftLeavesSum(root->right); } // return result return res; } /* Driver program to test above functions*/ int main() { // Let us a construct the Binary Tree struct Node *root = newNode(20); root->left = newNode(9); root->right = newNode(49); root->right->left = newNode(23); root->right->right = newNode(52); root->right->right->left = newNode(50); root->left->left = newNode(5); root->left->right = newNode(12); root->left->right->right = newNode(12); cout << "Sum of left leaves is " << leftLeavesSum(root); return 0; } |
Java
// Java program to find sum of all left leaves class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; // A utility function to check if a given node is leaf or not boolean isLeaf(Node node) { if (node == null ) return false ; if (node.left == null && node.right == null ) return true ; return false ; } // This function returns sum of all left leaves in a given // binary tree int leftLeavesSum(Node node) { // Initialize result int res = 0 ; // Update result if root is not NULL if (node != null ) { // If left of root is NULL, then add key of // left child if (isLeaf(node.left)) res += node.left.data; else // Else recur for left child of root res += leftLeavesSum(node.left); // Recur for right child of root and update res res += leftLeavesSum(node.right); } // return result return res; } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 9 ); tree.root.right = new Node( 49 ); tree.root.left.right = new Node( 12 ); tree.root.left.left = new Node( 5 ); tree.root.right.left = new Node( 23 ); tree.root.right.right = new Node( 52 ); tree.root.left.right.right = new Node( 12 ); tree.root.right.right.left = new Node( 50 ); System.out.println( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Mayank Jaiswal |
Python
# Python program to find sum of all left leaves # A Binary tree node class Node: # Constructor to create a new Node def __init__( self , key): self .key = key self .left = None self .right = None # A utility function to check if a given node is leaf or not def isLeaf(node): if node is None : return False if node.left is None and node.right is None : return True return False # This function return sum of all left leaves in a # given binary tree def leftLeavesSum(root): # Initialize result res = 0 # Update result if root is not None if root is not None : # If left of root is None, then add key of # left child if isLeaf(root.left): res + = root.left.key else : # Else recur for left child of root res + = leftLeavesSum(root.left) # Recur for right child of root and update res res + = leftLeavesSum(root.right) return res # Driver program to test above function # Let us constrcut the Binary Tree shown in the above function root = Node( 20 ) root.left = Node( 9 ) root.right = Node( 49 ) root.right.left = Node( 23 ) root.right.right = Node( 52 ) root.right.right.left = Node( 50 ) root.left.left = Node( 5 ) root.left.right = Node( 12 ) root.left.right.right = Node( 12 ) print "Sum of left leaves is" , leftLeavesSum(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // C# program to find sum of all left leaves public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { public Node root; // A utility function to check if a given node is leaf or not public virtual bool isLeaf(Node node) { if (node == null ) { return false ; } if (node.left == null && node.right == null ) { return true ; } return false ; } // This function returns sum of all left leaves in a given // binary tree public virtual int leftLeavesSum(Node node) { // Initialize result int res = 0; // Update result if root is not NULL if (node != null ) { // If left of root is NULL, then add key of // left child if (isLeaf(node.left)) { res += node.left.data; } else // Else recur for left child of root { res += leftLeavesSum(node.left); } // Recur for right child of root and update res res += leftLeavesSum(node.right); } // return result return res; } // Driver program public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(9); tree.root.right = new Node(49); tree.root.left.right = new Node(12); tree.root.left.left = new Node(5); tree.root.right.left = new Node(23); tree.root.right.right = new Node(52); tree.root.left.right.right = new Node(12); tree.root.right.right.left = new Node(50); Console.WriteLine( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Shrikant13 |
Output:
Sum of left leaves is 78
Time complexity of the above solution is O(n) where n is number of nodes in Binary Tree.
Following is Another Method to solve the above problem. This solution passes in a sum variable as an accumulator. When a left leaf is encountered, the leaf’s data is added to sum. Time complexity of this method is also O(n). Thanks to Xin Tong (geeksforgeeks userid trent.tong) for suggesting this method.
C++
// A C++ program to find sum of all left leaves #include <iostream> using namespace std; /* A binary tree Node has key, pointer to left and right children */ struct Node { int key; struct Node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointer. */ Node *newNode( char k) { Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } /* Pass in a sum variable as an accumulator */ void leftLeavesSumRec(Node *root, bool isleft, int *sum) { if (!root) return ; // Check whether this node is a leaf node and is left. if (!root->left && !root->right && isleft) *sum += root->key; // Pass 1 for left and 0 for right leftLeavesSumRec(root->left, 1, sum); leftLeavesSumRec(root->right, 0, sum); } // A wrapper over above recursive function int leftLeavesSum(Node *root) { int sum = 0; //Initialize result // use the above recursive function to evaluate sum leftLeavesSumRec(root, 0, &sum); return sum; } /* Driver program to test above functions*/ int main() { // Let us construct the Binary Tree shown in the // above figure int sum = 0; struct Node *root = newNode(20); root->left = newNode(9); root->right = newNode(49); root->right->left = newNode(23); root->right->right = newNode(52); root->right->right->left = newNode(50); root->left->left = newNode(5); root->left->right = newNode(12); root->left->right->right = newNode(12); cout << "Sum of left leaves is " << leftLeavesSum(root) << endl; return 0; } |
Java
// Java program to find sum of all left leaves class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } // Passing sum as accumulator and implementing pass by reference // of sum variable class Sum { int sum = 0 ; } class BinaryTree { Node root; /* Pass in a sum variable as an accumulator */ void leftLeavesSumRec(Node node, boolean isleft, Sum summ) { if (node == null ) return ; // Check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isleft) summ.sum = summ.sum + node.data; // Pass true for left and false for right leftLeavesSumRec(node.left, true , summ); leftLeavesSumRec(node.right, false , summ); } // A wrapper over above recursive function int leftLeavesSum(Node node) { Sum suum = new Sum(); // use the above recursive function to evaluate sum leftLeavesSumRec(node, false , suum); return suum.sum; } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 9 ); tree.root.right = new Node( 49 ); tree.root.left.right = new Node( 12 ); tree.root.left.left = new Node( 5 ); tree.root.right.left = new Node( 23 ); tree.root.right.right = new Node( 52 ); tree.root.left.right.right = new Node( 12 ); tree.root.right.right.left = new Node( 50 ); System.out.println( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Mayank Jaiswal |
Python
# Python program to find sum of all left leaves # A binary tree node class Node: # A constructor to create a new Node def __init__( self , key): self .key = key self .left = None self .right = None def leftLeavesSumRec(root, isLeft, summ): if root is None : return # Check whether this node is a leaf node and is left if root.left is None and root.right is None and isLeft = = True : summ[ 0 ] + = root.key # Pass 1 for left and 0 for right leftLeavesSumRec(root.left, 1 , summ) leftLeavesSumRec(root.right, 0 , summ) # A wrapper over above recursive function def leftLeavesSum(root): summ = [ 0 ] # initialize result # Use the above recursive fucntion to evaluate sum leftLeavesSumRec(root, 0 , summ) return summ[ 0 ] # Driver program to test above function # Let us construct the Binary Tree shown in the # above figure root = Node( 20 ); root.left = Node( 9 ); root.right = Node( 49 ); root.right.left = Node( 23 ); root.right.right = Node( 52 ); root.right.right.left = Node( 50 ); root.left.left = Node( 5 ); root.left.right = Node( 12 ); root.left.right.right = Node( 12 ); print "Sum of left leaves is" , leftLeavesSum(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // C# program to find sum of all left leaves public class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } // Passing sum as accumulator and implementing pass by reference // of sum variable public class Sum { public int sum = 0; } public class BinaryTree { public Node root; /* Pass in a sum variable as an accumulator */ public virtual void leftLeavesSumRec(Node node, bool isleft, Sum summ) { if (node == null ) { return ; } // Check whether this node is a leaf node and is left. if (node.left == null && node.right == null && isleft) { summ.sum = summ.sum + node.data; } // Pass true for left and false for right leftLeavesSumRec(node.left, true , summ); leftLeavesSumRec(node.right, false , summ); } // A wrapper over above recursive function public virtual int leftLeavesSum(Node node) { Sum suum = new Sum(); // use the above recursive function to evaluate sum leftLeavesSumRec(node, false , suum); return suum.sum; } // Driver program public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(9); tree.root.right = new Node(49); tree.root.left.right = new Node(12); tree.root.left.left = new Node(5); tree.root.right.left = new Node(23); tree.root.right.right = new Node(52); tree.root.left.right.right = new Node(12); tree.root.right.right.left = new Node(50); Console.WriteLine( "The sum of leaves is " + tree.leftLeavesSum(tree.root)); } } // This code is contributed by Shrikant13 |
Output:
Sum of left leaves is 78
Iterative Approach :
This is the Iterative Way to find the sum of the left leaves.
Idea is to perform Depth-First Traversal on the tree (either Inorder, Preorder or Postorder) using a stack and checking if the Left Child is a Leaf node. If it is, then add the nodes value to the sum variable
# Python program to find sum of all left leaves # A binary tree node class Node: # A constructor to create a new Node def __init__( self , key): self .key = key self .left = None self .right = None # Return the sum of left leaf nodes def sumOfLeftLeaves(root): if (root is None ): return # Using a stack for Depth-First Traversal of the tree stack = [] stack.append(root) # sum holds the sum of all the left leaves sum = 0 while len (stack) > 0 : currentNode = stack.pop() if currentNode.left is not None : stack.append(currentNode.left) # Check if currentNode's left child is a leaf node if currentNode.left.left is None and currentNode.left.right is None : # if currentNode is a leaf, add its data to the sum sum = sum + currentNode.left.data if currentNode.right is not None : stack.append(currentNode.right) return sum # Driver Code root = Tree( 20 ); root.left = Tree( 9 ); root.right = Tree( 49 ); root.right.left = Tree( 23 ); root.right.right = Tree( 52 ); root.right.right.left = Tree( 50 ); root.left.left = Tree( 5 ); root.left.right = Tree( 12 ); root.left.right.right = Tree( 12 ); print ( 'Sum of left leaves is {}' . format (sumOfLeftLeaves(root))) |
Output:
Sum of left leaves is 78
Thanks to Shubham Tambere for suggesting this approach.
leave a comment
0 Comments