Home » Data Structure

Sum of all right leaf nodes in a given tree

In this article, we are going to see how to find the sum of all right leaf nodes in a given tree?
Submitted by Radib Kar, on August 27, 2020

Right Leaf node means which is a leaf node and also right child of the parent. So, to do this we can use any of the traversal techniques we have learnt already. We can either use depth-first based traversal (inorder/preorder/postorder), or breadth-first based traversal (level order traversal). While traversing what we need is to keep checking whether the current node has any right child which is a leaf node too. If the node has then we add the right child node value with the cumulative sum.

In the below example,

We can see that the only right leaf node is 40, so the sum will be 40.

But in the below example,

The marked nodes are the right leaf nodes and thus sum would be: 19

Solution:

1) Using depth-first based traversals:

Here I have used inorder traversal to traverse the tree. The solution is pretty much the same as we did in Sum of all parents having child value X in the given tree. But, here the constraint is different and now the constraint is we need to sum up leaf nodes which are the right child of its parent node. Below is the detailed implementation.

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

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

//depth first traversal and summing
void dfs(TreeNode* root, int& sum)
{
    if (!root)
        return;
    //if it has right child and the child is leaf node 
    //then add the child value
    if (root->right && !root->right->left && !root->right->right)
        sum += root->right->val;

    dfs(root->left, sum);
    dfs(root->right, sum);
}

int rightLeafSum(TreeNode* root)
{
    //Code here
    int sum = 0;
    dfs(root, sum);
    return sum;
}

int main()
{
    //building the tree like example1
    TreeNode* root1 = new TreeNode(10);
    
    root1->left = new TreeNode(20);
    root1->right = new TreeNode(30);

    root1->right->left = new TreeNode(50);
    root1->right->right = new TreeNode(40);
    root1->right->left->left = new TreeNode(60);

    cout << "Sum of all right leaves in the Example1 is: " << rightLeafSum(root1) << endl;

    //building the tree like example2
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(3);
    root2->left->right = new TreeNode(8);
    root2->right->left = new TreeNode(5);
    root2->right->right = new TreeNode(4);
    root2->right->left->left = new TreeNode(6);
    root2->right->left->right = new TreeNode(7);

    cout << "Sum of all right leaves in the Example2 is: " << rightLeafSum(root2) << endl;
    
    return 0;
}

Output:

Sum of all right leaves in the Example1 is: 40
Sum of all right leaves in the Example2 is: 19

2) Using breadth-first traversal:

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

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

//breadth first traversal and summing
void bfs(TreeNode* root, int& sum)
{
    if (!root)
        return;

    queue<TreeNode*> q;
    q.push(root);
    //do a level order traversal and keep adding node values
    while (!q.empty()) {
        TreeNode* temp = q.front();
        q.pop();
        //if it has right child and the child is leaf node 
        //then add the child value
        if (temp->right && !temp->right->left && !temp->right->right)
            sum += temp->right->val;
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right)
            q.push(temp->right);
    }
}

int rightLeafSum(TreeNode* root)
{
    //Code here
    int sum = 0;
    bfs(root, sum);
    return sum;
}

int main()
{
    //building the tree like example1
    TreeNode* root1 = new TreeNode(10);
    root1->left = new TreeNode(20);
    root1->right = new TreeNode(30);

    root1->right->left = new TreeNode(50);
    root1->right->right = new TreeNode(40);
    root1->right->left->left = new TreeNode(60);

    cout << "Sum of all right leaves in the Example1 is: " << rightLeafSum(root1) << endl;

    //building the tree like example2
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(3);
    root2->left->right = new TreeNode(8);
    root2->right->left = new TreeNode(5);
    root2->right->right = new TreeNode(4);
    root2->right->left->left = new TreeNode(6);
    root2->right->left->right = new TreeNode(7);

    cout << "Sum of all right leaves in the Example2 is: " << rightLeafSum(root2) << endl;

    return 0;
}

Output:

Sum of all right leaves in the Example1 is: 40
Sum of all right leaves in the Example2 is: 19