Sum of leaf nodes at the deepest level in a binary tree

Finding sum of nodes at the deepest level in a binary tree

An idea behind finding the sum of nodes at the deepest level in a binary tree is to use Level Order tree traversal.
In Level-Order tree traversal, the data in the nodes is accessed level-wise from the top i.e from root level all the way down to the bottom of the tree.


Algorithm : Finding the sum of leaves at the deepest level in a binary tree using Level-Order tree traversal

1.    Create two queues / lists; one for storing the parent and the other for storing the children.
      Set result = 0, this will store the sum of leaves at the deepest level in a binary tree.
2.    Push the root node into the parent queue.
3.    While the parent queue or the child queue is not empty do the below
4.         While the parent queue is not empty
5.             Pop-out node P from the parent queue and add it to the result.
6.             If node P has children, add it to the queue for children.
7.         If the child queue is not empty, reset the result to 0.
7.         While the child queue is not empty
8.             Pop-out node C from the child queue and add it to the result.
9.             If node C has children, add it to the queue for the parent.
10.        If the parent queue is not empty, reset the result to 0.
11.    Return the result as the sum of nodes at the deepest level.


Sum_of_leaf_nodes_at_the_deepest_level

Data structure used for finding the sum of leaves at the deepest level in a binary tree using level order traversal : Queue

Time Complexity of finding the sum of leaves at the deepest level in a binary tree using level order traversal : 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++ : Finding the sum of leaves at the deepest level in a binary tree using level order tree traversal implemented in C++11

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

class Node {
public:
    Node(int n) : data(n), left(NULL), right(NULL) {
    }
    Node * left;
    Node * right;
    int data;
};

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

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

        if (!child_queue.empty())
            deepest_leaves_sum = 0;

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

            deepest_leaves_sum += node->data;

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

        if (!parent_queue.empty())
            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 *root = new Node(9);
    root->left = new Node(4);
    root->right = new Node(16);
    root->left->left  = new Node(3);
    root->left->right = new Node(7);
    root->left->right->left = new Node(6);
    root->left->right->left->left = new Node(5);
    root->left->right->right = new Node(8);
    root->right->left = new Node(12);
    root->right->right = new Node(18);
    root->right->right->right = new Node(25);
    root->right->right->right->left = new Node(20);
    root->right->right->right->right = new Node(36);

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

    // Cleanup
    delete root->right->right->right->right;
    delete root->right->right->right->left;
    delete root->right->right->right;
    delete root->right->right;
    delete root->right->left;
    delete root->left->right->right->left;
    delete root->left->right->right;
    delete root->left->right->left;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Output : The sum of leaves at the deepest level in a binary tree implemented in C++11

Sum of leaves at the deepest level : 61

Copyright (c) 2020, Algotree.org.
All rights reserved.