Given a Binary Tree rooted at root, the task is to find the sum of all leaf nodes which are left child of their parents and which also have their right sibling i.e, it’s a parent has also a right child.
Examples:
Input: 16
/ \
20 15
/ / \
100 21 25
/ / \ / \
27 14 9 7 6
/ \ \
17 12 2
Output: 24.
Explanation: The leaf nodes having values 7 and 17 only have a right sibling.Input: 12
/ \
13 10
/ \
14 15
/ \
22 23Output: 49
Approach: The idea is to use recursion to solve this problem. Start traversing from the root node. For every node check if it is NULL if true then return 0. If both children are NULL return 0. If both children are not NULL:
- If left is a leaf node then return root->left->data + value getting on traversing the right child.
- Else return value getting on traversing the left child + value getting on traversing the right child
Following the steps below to solve the problem:
- If root equals null or a leaf-node, then return 0.
- If root has both the children, then perform the following tasks:
- If the left child of root is a leaf node then return root->left->data + sumOfLeft(root->right).
- Else, return the summation of sumofLeft(root->left) and sumofLeft(root->right).
- Else if, there is root->left, then return sumofLeft(root->left).
- Else return sumofLeft(root->right).
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Node of the binary tree.class Node {public: int data; Node *left, *right; Node(int data) { this->data = data; this->left = NULL; this->right = NULL; }};// Function to return the sum of// left leaf node having right sibling.int sumOfLeft(Node* root){ // If root node is NULL if (root == NULL) return 0; // If root node is a leaf node // Note: It is not for left leaf // node having right sibling if (root->left == NULL && root->right == NULL) return 0; // If node has both the child if (root->left != NULL && root->right != NULL) { // If its left node is leaf node if (root->left->left == NULL && root->left->right == NULL) { // Returning the sum of // left node data // and the value obtained by // traversing right child return root->left->data + sumOfLeft(root->right); } else { // Returning sum of values // obtained by traversing // both the child return sumOfLeft(root->left) + sumOfLeft(root->right); } } // If there is only left child else if (root->left != NULL) { return sumOfLeft(root->left); } // If only right child is left return sumOfLeft(root->right);}// Driver Codeint main(){ // Binary tree construction Node* root = new Node(12); root->left = new Node(13); root->right = new Node(10); root->right->left = new Node(14); root->right->right = new Node(15); root->right->right->left = new Node(22); root->right->right->right = new Node(23); cout << sumOfLeft(root); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Node of the binary tree.static class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = null; this.right = null; }};// Function to return the sum of// left leaf node having right sibling.static int sumOfLeft(Node root){ // If root node is null if (root == null) return 0; // If root node is a leaf node // Note: It is not for left leaf // node having right sibling if (root.left == null && root.right == null) return 0; // If node has both the child if (root.left != null && root.right != null) { // If its left node is leaf node if (root.left.left == null && root.left.right == null) { // Returning the sum of // left node data // and the value obtained by // traversing right child return root.left.data + sumOfLeft(root.right); } else { // Returning sum of values // obtained by traversing // both the child return sumOfLeft(root.left) + sumOfLeft(root.right); } } // If there is only left child else if (root.left != null) { return sumOfLeft(root.left); } // If only right child is left return sumOfLeft(root.right);}// Driver Codepublic static void main(String[] args){ // Binary tree construction Node root = new Node(12); root.left = new Node(13); root.right = new Node(10); root.right.left = new Node(14); root.right.right = new Node(15); root.right.right.left = new Node(22); root.right.right.right = new Node(23); System.out.print(sumOfLeft(root));}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Node of the binary tree.class Node: def __init__(self, data): self.data = data; self.left = None; self.right = None;# Function to return the sum of# left leaf Node having right sibling.def sumOfLeft(root): # If root Node is None if (root == None): return 0; # If root Node is a leaf Node # Note: It is not for left leaf # Node having right sibling if (root.left == None and root.right == None): return 0; # If Node has both the child if (root.left != None and root.right != None): # If its left Node is leaf Node if (root.left.left == None and root.left.right == None): # Returning the sum of # left Node data # and the value obtained by # traversing right child return root.left.data + sumOfLeft(root.right); else: # Returning sum of values # obtained by traversing # both the child return sumOfLeft(root.left) + sumOfLeft(root.right); # If there is only left child elif(root.left != None): return sumOfLeft(root.left); # If only right child is left return sumOfLeft(root.right);# Driver Codeif __name__ == '__main__': # Binary tree construction root = Node(12); root.left = Node(13); root.right = Node(10); root.right.left = Node(14); root.right.right = Node(15); root.right.right.left = Node(22); root.right.right.right = Node(23); print(sumOfLeft(root));# This code is contributed by Rajput-Ji |
C#
// C# program for the above approachusing System;public class GFG{ // Node of the binary tree. class Node { public int data; public Node left, right; public Node(int data) { this.data = data; this.left = null; this.right = null; } }; // Function to return the sum of // left leaf node having right sibling. static int sumOfLeft(Node root) { // If root node is null if (root == null) return 0; // If root node is a leaf node // Note: It is not for left leaf // node having right sibling if (root.left == null && root.right == null) return 0; // If node has both the child if (root.left != null && root.right != null) { // If its left node is leaf node if (root.left.left == null && root.left.right == null) { // Returning the sum of // left node data // and the value obtained by // traversing right child return root.left.data + sumOfLeft(root.right); } else { // Returning sum of values // obtained by traversing // both the child return sumOfLeft(root.left) + sumOfLeft(root.right); } } // If there is only left child else if (root.left != null) { return sumOfLeft(root.left); } // If only right child is left return sumOfLeft(root.right); } // Driver Code public static void Main(String[] args) { // Binary tree construction Node root = new Node(12); root.left = new Node(13); root.right = new Node(10); root.right.left = new Node(14); root.right.right = new Node(15); root.right.right.left = new Node(22); root.right.right.right = new Node(23); Console.Write(sumOfLeft(root)); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Node of the binary tree. class Node { constructor(d) { this.data = d; this.left = null; this.right = null; } }; // Function to return the sum of // left leaf node having right sibling. function sumOfLeft(root) { // If root node is null if (root == null) return 0; // If root node is a leaf node // Note: It is not for left leaf // node having right sibling if (root.left == null && root.right == null) return 0; // If node has both the child if (root.left != null && root.right != null) { // If its left node is leaf node if (root.left.left == null && root.left.right == null) { // Returning the sum of // left node data // and the value obtained by // traversing right child return root.left.data + sumOfLeft(root.right); } else { // Returning sum of values // obtained by traversing // both the child return sumOfLeft(root.left) + sumOfLeft(root.right); } } // If there is only left child else if (root.left != null) { return sumOfLeft(root.left); } // If only right child is left return sumOfLeft(root.right); } // Driver Code // Binary tree construction let root = new Node(12); root.left = new Node(13); root.right = new Node(10); root.right.left = new Node(14); root.right.right = new Node(15); root.right.right.left = new Node(22); root.right.right.right = new Node(23); document.write(sumOfLeft(root)); // This code is contributed by Potta Lokesh </script> |
Output
49
Time Complexity: O(N) where N is the total number of nodes
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
