Algotree > Algorithms > Tree & Graph Traversal > Sum of leaf nodes at the deepest level

Sum of leaf nodes at the deepest level

The idea behind finding the sum of nodes at the deepest level in a binary tree is to use Level Order tree traversal.
As we do a Level-Order tree traversal, we find the sum of data of all the nodes in that level. If we encounter another level below the current one, we reset the earlier found sum and find the sum in the current level.

Sum_of_leaf_nodes_at_the_deepest_level

Algorithm : Deepest_Leaves_Sum()

1.    Create two queues / lists;
      Parent_Queue for storing the parent.
      Child_Queue for storing the children.
      Initialize result = 0, for storing the sum of leaves at every level.
2.    Push the root node into the parent queue.
3.    While the parent queue or the child queue is not empty, do
4.         While the parent queue is not empty, do
5.             Pop-out node P from the parent queue and add it to the result.
6.             If node P has children, then add it to the queue for children.
7.         If the child queue is not empty, then reset the result to 0.
8.         While the child queue is not empty, do
9.             Pop-out node C from the child queue and add it to the result.
10.             If node C has children, then add it to the queue for the parent.
11.        If the parent queue is not empty, then reset the result to 0.
12.    Return the result as the sum of nodes at the deepest level.

Data structure used : Queue

Time Complexity : O ( n ), where n is the number of nodes in the tree. As the push O ( 1 ) and pop O ( 1 ) operations happen only once for every node in the tree the time complexity is O ( n ).

C++ program for finding the sum of leaves at the deepest level in a binary tree

#include<iostream>
#include<queue>
using namespace std;

class Node {
    public:
    int val;
    Node *left;
    Node *right;
    Node() : val(0), left(nullptr), right(nullptr) {}
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
    Node(int x, Node *left, Node *right) : val(x), left(left), right(right) {}
};

int DeepestLeavesSum (Node * root) {

    if(root == NULL)
       return 0;

    queue<Node *> parent_queue, child_queue;

    parent_queue.push(root);

    // Level 0 corresponds to the top of the tree i.e at the root level
    int level = 0;
    int deepest_leaves_sum = 0;

    while (!parent_queue.empty() or !child_queue.empty()) {

        while (!parent_queue.empty()) {
            Node * node = parent_queue.front();
            parent_queue.pop();

            deepest_leaves_sum += node->val;

            if (node->left != NULL)
                child_queue.push(node->left);
            if (node->right != NULL)
                child_queue.push(node->right);
        }

        if (!child_queue.empty()) // As a new level is reached, reset the earlier found sum.
            deepest_leaves_sum = 0;

        while (!child_queue.empty()) {
            Node * node = child_queue.front();
            child_queue.pop();

            deepest_leaves_sum += node->val;

            if (node->left != NULL)
                parent_queue.push(node->left);
            if (node->right != NULL)
                parent_queue.push(node->right);
        }

        if (!parent_queue.empty()) // As a new level is reached, reset the earlier found sum.
            deepest_leaves_sum = 0;
    }
    return deepest_leaves_sum;
}

int main() {

/* Constructed binary tree is
               9
             /   \
            4     16
          /  \   /  \
         3   7  12   18
            / \       \
           6   8      25
          /          /  \
         5          20  36
*/
    Node node_5 (5, nullptr, nullptr);
    Node node_6 (6, &node_5, nullptr);
    Node node_8 (8, nullptr, nullptr);
    Node node_7 (7, &node_6, &node_8);
    Node node_3 (3, nullptr, nullptr);
    Node node_4 (4, &node_3, &node_7);
    Node node_12 (12, nullptr, nullptr);
    Node node_20 (20, nullptr, nullptr);
    Node node_36 (36, nullptr, nullptr);
    Node node_25 (25, &node_20, &node_36);
    Node node_18 (18, nullptr, &node_25);
    Node node_16 (16, &node_12, &node_18);
    Node node_9 (9, &node_4, &node_16);

    cout << "Sum of leaves at the deepest level : " << DeepestLeavesSum (&node_9) << endl;

    return 0;
}

Output

Sum of leaves at the deepest level : 61