Sum of nodes in a binary tree having only the left child nodes
Given a binary tree, the task is to find the sum of binary tree nodes having only the left child nodes.
Example:
Input: 8
/ \
3 7
/ \ /
5 6 0
/ /
1 2
Output: 18
Explanation: Nodes with values 5, 6, and 7 are the ones that have only the left child nodesInput: 2
/ \
3 1
/ /
5 6
Output: 4
Approach: The given problem can be solved by traversing the binary tree using postorder traversal. The idea is to check if a node contains only a left child node, and add the value of the current node to the answer if the condition is true. Below steps can be followed to solve the problem:
- Traverse the binary tree using postorder traversal
- If the root is null, then return 0
- Use recursion on the left subtree and store its answer in a variable left
- Use recursion on the right subtree and store its answer in a variable right
- If root.left != null && root.right == null, then return the value of root.val + left + right
- Else return left + right
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; struct Node { int val; Node *left; Node *right; Node( int value) { val = value; left = NULL; right = NULL; } }; // Function to find the sum of nodes // having only left child node int sumLeftChild(Node *root) { if (root == NULL) return 0; // Sum of nodes having only left // child node from left subtree int left = sumLeftChild(root->left); // Sum of nodes having only left // child node from right subtree int right = sumLeftChild(root->right); // If current node has only left // child node return the sum from // left subtree + right // subtree + root->val if (root->left != NULL && root->right == NULL) { return root->val + left + right; } // Return the value from left // and right subtrees return left + right; } // Driver code int main() { // Initialize the tree Node *root = new Node(2); root->left = new Node(3); root->right = new Node(4); root->left->left = new Node(5); root->right->left = new Node(7); cout << (sumLeftChild(root)); return 0; } // This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the sum of nodes // having only left child node public static int sumLeftChild(Node root) { if (root == null ) return 0 ; // Sum of nodes having only left // child node from left subtree int left = sumLeftChild(root.left); // Sum of nodes having only left // child node from right subtree int right = sumLeftChild(root.right); // If current node has only left // child node return the sum from // left subtree + right // subtree + root.val if (root.left != null && root.right == null ) { return root.val + left + right; } // Return the value from left // and right subtrees return left + right; } // Driver code public static void main(String[] args) { // Initialize the tree Node root = new Node( 2 ); root.left = new Node( 3 ); root.right = new Node( 4 ); root.left.left = new Node( 5 ); root.right.left = new Node( 7 ); System.out.println(sumLeftChild(root)); } static class Node { int val; Node left, right; public Node( int val) { this .val = val; } } } |
Python
# Python code for the above approach class Node: def __init__( self , value): self .val = value self .left = None self .right = None # Function to find the sum of nodes # having only left child node def sumLeftChild(root): if root is None : return 0 # Sum of nodes having only left # child node from left subtree left = sumLeftChild(root.left) # Sum of nodes having only left # child node from right subtree right = sumLeftChild(root.right) # If current node has only left # child node return the sum from # left subtree + right # subtree + root->val if root.left is not None and root.right is None : return root.val + left + right # Return the value from left # and right subtrees return left + right # Driver code if __name__ = = '__main__' : # Initialize the tree root = Node( 2 ) root.left = Node( 3 ) root.right = Node( 4 ) root.left.left = Node( 5 ) root.right.left = Node( 7 ) print (sumLeftChild(root)) # This code is contributed by adityamaharshi21 |
C#
// C# implementation for the above approach using System; public class GFG { // Function to find the sum of nodes // having only left child node public static int sumLeftChild(Node root) { if (root == null ) return 0; // Sum of nodes having only left // child node from left subtree int left = sumLeftChild(root.left); // Sum of nodes having only left // child node from right subtree int right = sumLeftChild(root.right); // If current node has only left // child node return the sum from // left subtree + right // subtree + root.val if (root.left != null && root.right == null ) { return root.val + left + right; } // Return the value from left // and right subtrees return left + right; } // Driver code public static void Main(String[] args) { // Initialize the tree Node root = new Node(2); root.left = new Node(3); root.right = new Node(4); root.left.left = new Node(5); root.right.left = new Node(7); Console.WriteLine(sumLeftChild(root)); } public class Node { public int val; public Node left, right; public Node( int val) { this .val = val; } } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation for the above approach class Node { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } // Function to find the sum of nodes // having only left child node function sumLeftChild(root) { if (root == null ) return 0; // Sum of nodes having only left // child node from left subtree let left = sumLeftChild(root.left); // Sum of nodes having only left // child node from right subtree let right = sumLeftChild(root.right); // If current node has only left // child node return the sum from // left subtree + right // subtree + root.val if (root.left != null && root.right == null ) { return root.val + left + right; } // Return the value from left // and right subtrees return left + right; } // Driver code // Initialize the tree let root = new Node(2); root.left = new Node(3); root.right = new Node(4); root.left.left = new Node(5); root.right.left = new Node(7); document.write(sumLeftChild(root)); // This code is contributed by saurabh_jaiswal. </script> |
7
Time Complexity: O(N)
Auxiliary space: O(n) for implicit call stack as using recursion
Contact Us