Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach 1: Using recursion
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Approach 2: Using Iteration
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
In a binary tree, what is a leaf node?
4.2.
What is the BST in order traversal time complexity?
4.3.
What is the total time complexity of all values stored in an n-node binary search tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find the sum of all right leaves in a given Binary Tree

Author Palak Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss a Binary Tree problem. We are provided with a  binary tree and the task is to find the sum of all right leaves in a given binary tree. The term "right leaf node" refers to a leaf node that is the right child of a parent. We must constantly check to see if the current node has any right children that are also leaf nodes while traversing. If the node has, we combine the cumulative sum with the appropriate child node value.

Problem Statement

Ninja has a binary tree. The total nodes in the tree are n. He gave the tree to you. He said he wanted to check the sum of all right leaf nodes of the respective binary tree. But, the problem is that he cannot check it alone as he is busy with other work. Can you help him with the situation and Calculate the sum of all right leaves nodes in the given binary tree.

Before deep-diving into the solution to this problem, we should look at some examples to help us understand the situation better.

Sample Examples

Example 1:

Here, as shown in the diagram we have two right leaf nodes i.e. 3 and 6

example 1

Output:

9

 

Explanation:

The Right leaf nodes of the tree are: 3, 6
Therefore, Sum = 3 + 6 = 9

 

Example 2:

Here, as shown in the diagram we have only one right leaf node i.e. 6

example 2

Output:

6

 

Explanation: 

The right leaf node of the tree is: 6
Therefore, Sum = 6

Approach 1: Using recursion

The goal is to move up the tree starting at the root and determine whether or not each node is a leaf node. Add the right leaf's data to the sum variable if the node is the right leaf.

Algorithm

  • From root to leaf, we will traverse the tree.
  • Verify whether or not the node is a leaf node.
  • Add a node to the sum if it is a left leaf node.
  • After traversing the entire tree. Print Sum.

Implementation

#include <iostream>
using namespace std;


//Using recursion to find the sum of all right nodes of the binary tree


struct Node{
   int key;
   struct Node* left, *right;
};


Node *newNodeofBT(char k){
   Node *node = new Node;
   node->key = k;
   node->right = node->left = NULL;
   return node;
}


bool isLeafNodeofBT(Node *node){
   if (node == NULL)
      return false;
   if (node->left == NULL && node->right == NULL)
      return true;
   return false;
}


int findRGTLeavesSum(Node *root){
   int sum = 0;
   if (root != NULL){
      if (isLeafNodeofBT(root->right))
         sum += root->right->key;
      else
         sum += findRGTLeavesSum(root->right);
         sum += findRGTLeavesSum(root->left);
   }
   return sum;
}


//Main Function of the Program
int main(){
   struct Node *root = newNodeofBT(5);
   root->left = newNodeofBT(4);
   root->right = newNodeofBT(6);
   root->left->left = newNodeofBT(2);
   root->left->right = newNodeofBT(1);
   root->right->left = newNodeofBT(9);
   root->right->right = newNodeofBT(7);
   cout<<" Sum of all right leaves of the Binary tree is "<<findRGTLeavesSum(root);
   return 0;
}

 

Output

Sum of all right leaves of the Binary tree is 8

 

Complexity Analysis

Time Complexities: O(n), The recursive function takes O(n) time to traverse the whole binary tree. Here n is the number of nodes in the binary tree. 

Space Complexities: O(n), The stack used in this recursive function takes O(n) extra space. So the space complexity is O(n).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2: Using Iteration

The idea is to move through the tree and determine whether a leaf node is present whenever we reach the appropriate node. In case it's a leaf node, raise the sum.We use a queue in this approach.

Algorithm

  • We will traverse the tree using the depth-first search
  • Then determine whether the current node is a right leaf. 
  • If so, include its value in the total; 
  • Otherwise, leave. 
  • Print the total at the end.

Implementation

#include<bits/stdc++.h>
using namespace std;


//using Iteration to find sum of all right nodes of the binary tree


struct Node{
   int key; struct Node* left, *right;
};
Node *newNodeOfBT(char k){
   Node *node = new Node;
   node->key = k;
   node->right = node->left = NULL;
   return node;
}
int findRGTLeavesSum(Node* root){
   if(root == NULL) return 0;


      stack<Node*> treeNodes;
   treeNodes.push(root); int sum = 0;
   while(treeNodes.size() > 0){
      Node* currentNode = treeNodes.top();
      treeNodes.pop();
      if (currentNode->right != NULL){
         treeNodes.push(currentNode->right);
         if(currentNode->right->right == NULL &&
            currentNode->right->left == NULL){
            sum += currentNode->right->key ;
         }
      }
      if (currentNode->left != NULL)
         treeNodes.push(currentNode->left);
   }
   return sum;
}
//Main function of the program
int main(){
   Node *root = newNodeOfBT(5);
   root->left= newNodeOfBT(4);
   root->right = newNodeOfBT(6);
   root->left->left = newNodeOfBT(2);
   root->left->right = newNodeOfBT(1);
   root->right->left = newNodeOfBT(9);
   root->right->right= newNodeOfBT(7);
   cout<<"Sum of all right leaves of the Binary tree is "<<findRGTLeavesSum(root);
   return 0;
}

 

Output

Sum of all right leaves of the Binary tree is 8

 

Complexity Analysis

Time Complexities: O(n), To traverse the complete binary tree this approach also takes O(n) time. So, the overall time complexity is O(n).

Space Complexities: O(n), We are using the stack to store the value of the visited node. So the extra space required is O(n).

Check out this problem - Root To Leaf Path

Frequently Asked Questions

In a binary tree, what is a leaf node?

A node with two empty child nodes is called a leaf node. We say that p is the parent of q and that q is a child of p if q is the root of p's subtree and p is a node. Sibling nodes are two nodes with the same parents.

What is the BST in order traversal time complexity?

Each node in an inorder tree traversal is only visited once if there are n nodes, so the complexity is O(n).

What is the total time complexity of all values stored in an n-node binary search tree?

As there are n nodes in the tree and we are calculating the maximum sum of the node-to-leaf paths of each node's left and right subtree, which takes O(n) time, the solution's time complexity is O(n2).

Conclusion

As discussed in this article, the problem "Find the sum of all right leaves in a given Binary Tree" asks you to return the sum of all the leaf nodes that are the right child of their parent of the given binary tree. We use the traversal technique to get the desired result.

We hope that this article has helped you enhance your knowledge regarding the subject of Binary Tree.

After reading about the traversal of the Binary tree, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about  Maximum Width In Binary Tree and Special Binary Tree. Also, see Binary Tree Zigzag Traversal and Number of balanced binary trees.

You can also practice some relevant problems at the code studio, such as:

  1. Preorder Binary Tree
  2. Construct Binary Tree From Inorder and Preorder Traversal
  3. Top View Of Binary Tree
  4. Height of the Binary Tree From Inorder and Level Order Traversal


Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

 

 

Previous article
Find Sum of All Left Leaves in a Given Binary Tree
Next article
Sum of all numbers that are formed from root to leaf paths
Live masterclass