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

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Sum of all right leaves of the Binary tree is 8

You can also try this code with Online C++ Compiler

Run Code

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(n²).

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 Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!