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
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Approach 2
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a binary tree's diameter?
4.2.
What is the minimum time required to find the longest path of a binary tree?
4.3.
How do you determine whether two trees are the same?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find the Sum of Nodes on the Longest Path from the Root to the Leaf Node

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

You should master trees to ace your coding interview for a position in software engineering. They are also essential to many other data structures and regularly come up in coding interviews.

Let's look at a common tree question of finding the sum of nodes on the longest path from the root to the leaf node.

Problem Statement

Ninja has come to visit his girlfriend in her town. Ninja will take her for a long drive through the city to impress her. The town is divided into N equal rose garden areas(N nodes) connected by N-1 roadways(N-1 edges). Each garden contains a different number of red roses(node’s value). There is no self-connecting route.

Ninja’s girlfriend is fond of red roses. Surprisingly, Ninja has come to know that the amount of an effect he will have on her depends entirely on time he will spend with her throughout the journey.

Assume that each road linking two distinct garden areas is the same length. Ninja will start his long drive from his girlfriend’s house(root node). 

If he takes her on the longest route, his girlfriend will be impressed by him. He would also like to give all of the red roses collected by driving down the longest road.

Help Ninja discover the number of red roses on the longest path.

 

In simpler terms, we need to calculate the sum of nodes on the longest path from the root node to the leaf node.

When two or more paths compete to be the longest, the path with the maximum sum of nodes is considered.

 

Constraints:

  • 1 ≤ Nuber of nodes ≤ 100000
  • 1 ≤ Value of nodes ≤ 100000

Sample Examples

Input:

                                                         

Output:

The sum of nodes on the longest part from root to leaf node is 15.

Explanation:

                                                          

The longest root to leaf path includes the highlighted nodes 4 -> 6 -> 2-> 3 having the sum of (4 + 6 + 2+ 3) = 15.

 

Input:

                                                           

Output:

The sum of nodes on the longest part from root to leaf node is 23.

Explanation:

                                                               

We have the three longest root-to-leaf paths, which include 
nodes 4 -> 8 ->1->10
nodes 4 -> 5 ->3->7
nodes 4 -> 5 ->3->9
The path with the maximum number of nodes is considered in this situation.
So our output includes the highlighted nodes having the sum of (4 + 8 + 1+ 10) = 23.

Approach 1

We can break down this  problem into two small problems:

  • Find the maximum sum in a binary tree from the root node to any leaf node.
  • Print the binary tree's root-to-leaf path with the highest sum.

We will recursively calculate the sum of nodes on the longest path from the root to the leaf node.

Algorithm

  1. We will create a recursive function to find the sum of nodes on the longest path.
    1. We will pass the root element, current sum, current length, maximum length, and maximum sum as arguments of the recursive function.
    2. If the root will be equal to NULL and if the maximum length will be smaller than the current length:
      1. We will update the maximum length and the maximum sum.

         
  2. Recursively call the function for the Left Subtree.
    1. As arguments, we will pass the root-left element, current sum+ root-data, current length +1, maximum length, and maximum sum.

       
  3. Similarly, call the function recursively for the Right Subtree.
    1. As arguments, we will pass the root-right element, current sum+ root-data, current length +1, maximum length, and maximum sum.

Implementation

#include <bits/stdc++.h>
using namespace std;
// Nodes of the binary tree
struct Nodes {
          int data;
          Nodes* left, *right;
};


// function to get a new node
Nodes* newNode(int data)
{
         // allocating memory for the node
           Nodes* getNode = (Nodes*)malloc(sizeof(Nodes));

           getNode->data = data;
           getNode->left = getNode->right = NULL;
           return getNode;
}


// function to find the sum of nodes on the
// longest path from root to leaf node
void SumlongestPath(Nodes* root, int crnt_sum, int length, int& maxLen, int& maxSum)
{
           // if true,traverse a root to leaf path
           if (!root) {
                          // update maximum length and maximum sum
                          if (maxLen < length) {
                                        maxLen = length;
                                        maxSum = crnt_sum;
                          } else if (maxLen == length && maxSum < crnt_sum)
                                        maxSum = crnt_sum;
                    return;
}


// recursive function for left subtree
SumlongestPath(root->left, crnt_sum + root->data, length + 1, maxLen, maxSum);

// recursive function for right subtree
SumlongestPath(root->right, crnt_sum + root->data, length + 1, maxLen, maxSum);
}

// utility function to find the sum 
int SumlongestPathUtil(Nodes* root)
{
            // if tree is NULL, then the sum is 0
             if (!root)
                       return 0;
             int maxSum = INT_MIN, maxLen = 0;

             // finding the maximum sum 'maxSum' for the
            // maximum length root to leaf path
    SumlongestPath(root, 0, 0, maxLen, maxSum);
         // required maximum sum
            return  maxSum;
}


// Driver code
int main()
{
         // binary tree formation
         Nodes* root = newNode(4);
         root->left = newNode(8);
         root->right = newNode(5);  
         root->left->left = newNode(2); 
         root->left->right = newNode(1);
         root->right->left = newNode(3); 
         root->right->right = newNode(9); 
         root->left->right->left = newNode(6);


         cout << "The sum of nodes on the longest part from root to leaf node is "<< SumlongestPathUtil(root);
         return 0;
}

 

Output:

The sum of nodes on the longest part from root to leaf node is 19

Complexity Analysis

  • Time Complexity: The time complexity of the above solution is O(n). Since we need linear time for traversing the tree in a postorder manner.
     
  • Space Complexity: We need an extra O(n) space to store the subproblems' value. So, the space complexity of the above solution is O(n).

Here n is the size of the binary tree.

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

We will use level order traversal in this approach to find the sum of nodes on the longest path from the root to the leaf node.

Algorithm

  1. Make a structure that contains the path's current Node, level, and sum.
  2. We will push the root element with the root's data set to the value of sum and a level of 0.
  3. As necessary, update the maximum sum and maximum length by popping the front element from the queue.
  4. If present, push the left and right nodes.
  5. Repeat this for each node in the binary tree.

Implementation

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

struct Nodes
{
    Nodes* left;
    Nodes* right;
    int data;
   
    //constructor to set the data of the newly created tree node
    Nodes(int element){
      data = element;
      this->left = nullptr;
      this->right = nullptr;
   }
};


int SumlongestPath(Nodes* root){

/* structure to store current Node,it's level and sum*/
struct Element{
         Nodes* data;
         int lvl;
         int sum;
};


/*
maxSum stores the maximum sum
maxLevel stores maximum level
*/
int maxSum = root->data,maxLevel = 0;


/* queue to implement the level order traversal */

list<Element> queue;
Element n;


/* Each element variable stores the current Node, its level, sum*/
n.data = root;
n.lvl = 0;
n.sum = root->data;


/* push the root element to queue*/
queue.push_back(n);


/* do the level order traversal on the tree*/
while(!queue.empty()){

      Element front = queue.front();
      Nodes* crnt = front.data;
      queue.pop_front();



      if(front.lvl > maxLevel){
            maxSum = front.sum;
            maxLevel = front.lvl;
      }

      else if(front.lvl == maxLevel && front.sum > maxSum)
      maxSum = front.sum;


      /* if exists push the left element*/
      if(crnt->left){
            n.data = crnt->left;
            n.sum = n.data->data;
            n.sum += front.sum;
            n.lvl = front.lvl+1;
       queue.push_back(n);
     }

      /*if exists push the right element*/
      if(crnt->right){
            n.data = crnt->right;
            n.sum = n.data->data;
            n.sum += front.sum;
            n.lvl = front.lvl+1;
       queue.push_back(n);
     }
  }


 return maxSum;
}

//Main function
int main() {


  Nodes* root = new Nodes(4); 
  root->left = new Nodes(8); 
  root->right = new Nodes(5);
  root->left->left = new Nodes(2);
  root->left->right = new Nodes(1);
  root->right->left = new Nodes(3);
  root->right->right = new Nodes(9);
  root->left->right->left = new Nodes(6);

  cout << "The sum of nodes on the longest part from root to leaf node is " <<SumlongestPath(root) << "\n";
  return 0;
}

 

Output:

The sum of nodes on the longest part from root to leaf node is 19

Complexity Analysis

Time Complexity: The time complexity of the above solution is O(n). Since we need linear time for level order traversal of the binary tree.

Space Complexity: We need an extra O(n) space to implement the queue. So, the space complexity of the above solution is O(n).

Here n is the size of the binary tree.

Frequently Asked Questions

What is a binary tree's diameter?

The distance between any two nodes in a binary tree that is the longest is the tree's diameter. The root may or may not be crossed by this path. The number of edges connecting two nodes measures the path's length.

What is the minimum time required to find the longest path of a binary tree?

The minimum time complexity required to traverse the binary tree and find the longest path is O(n), where n is the size of the binary tree.

How do you determine whether two trees are the same?

They are similar if the data and structure are identical in two binary trees. This can be accomplished by comparing the data and designs of both trees while traversing them.

The algorithm that will allow us to do this is as follows:

  1. Verify the root node's data (tree1 data == tree2 data).
  2. Recursively check the left subtree. (tree1->left subtree, tree2->left subtree).
  3. Similarly, check for the right subtree.
  4. If all the above steps are true, return ‘the trees are identical.’

Conclusion

This article discussed the most commonly asked binary tree problem of finding the sum of nodes on the longest path from the root to the leaf node. We discussed two approaches to solve the given situation: finding the sum of nodes on the longest path.

This article is related to the binary tree, so it is recommended to visit our curated section of Binary trees at the Coding Ninjas Studio library, where you can learn Print the longest path from the root to the leaf node,  Binary tree traversalsTypes of Binary treesvarious operations on a binary tree, and different problems related to binary tree.

You can also visit our curated sections of BSTAVL treeGraphTrieDynamic programming, and many more.

Here are some of the widespread binary tree problems for your coding practice:

  1. Longest Univalue Path
  2. Boundary Traversal of Binary Tree
  3. Time to burn Tree
  4. Maximum path sum between two leaves
  5. Children sum property and many more at Coding Ninjas Studio.
     

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!

Live masterclass