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 Example 
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Algorithm Complexity
3.
Efficient Approach
3.1.
Implementation in C++
3.1.1.
Algorithm Complexity
4.
Frequently Asked Questions
4.1.
What are binary search trees used for?
4.2.
What is the difference between tree depth and height?
4.3.
What is the degree of a node?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sum of heights of all individual nodes in a binary tree

Author Prerna Tiwari
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing the problem of finding the sum of heights of all individual nodes in a binary tree. We will be discussing two approaches to solve this problem, but first, let us quickly learn about the binary tree.

binary tree is a data structure in which each parent node has no more than two children. A binary tree node is made up of three components

  • data
  • pointer to left
  • pointer to right


Height of nodes

  • Height of a node: number of edges from the node to the deepest leaf.
  • Height of a tree: the height of the root.

Let us understand the problem statement of finding the sum of heights of all individual nodes in a binary tree

Problem Statement

We will have a binary tree containing n nodes in the problem and we have to find the sum of the heights of all individual nodes in the tree. 

Before we dive deep into the solution to this problem, we should look at an example to understand the problem of the sum of heights of all individual nodes in a binary tree.

Sample Example
 

Output:

Height of Node 1 - 3
Height of Node 2 - 2
Height of Node 3 - 2
Height of Node 4 - 1
Height of Node 5 - 1
Height of Node 6 - 1
Height of Node 7 - 1
Hence the sum of heights of all nodes equals to (3+2+2+1+1+1+1) = 11

Brute Force Approach

The brute force approach to finding the sum of heights of all individual nodes in a binary tree is to traverse the tree in any order (preorder, postorder, or inorder ) and find the heights of each node. Then add the heights of each node for the answer.

Algorithm

  • To solve this problem, we will make two functions and call them recursively.
  • One function will calculate the height of the individual nodes.
  • And the other function will calculate the sum of heights of all individual nodes.
  • To calculate the height of each node, we find out the height of the left subtree and right subtree and pick the maximum among them, thereafter increasing the value by one.


We can traverse the tree in any order; here, we have used preorder traversal.

Implementation in C++

#include <bits/stdc++.h>

// basic node structure
struct Node
{
   int data;
   struct Node *left;
   struct Node *right;
};

// new node
struct Node *newNode(int data)
{
   struct Node *Node = (struct Node *)
   malloc(sizeof(struct Node));
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;

   return (Node);
}

// function to find max
int findMax(int a, int b)
{
   if (a >= b)
      return a;
   else
      return b;
}

// finding height of individual nodes
int findHeight(Node *root)
{
   // Base case:
   if (root == NULL)
      return 0;

   return findMax(findHeight(root->left), findHeight(root->right)) + 1;
}

// Finding total height using preorder traversal
int totalHeight(struct Node *root)
{
   if (root == NULL)
      return 0;

   return findHeight(root) + totalHeight(root->left) + totalHeight(root->right);
}

// Driver code
int main()
{
   struct Node *root = newNode(6);

   root->left = newNode(4);
   root->right = newNode(8);
   root->left->left = newNode(2);
   root->left->right = newNode(3);
   printf("Sum of heights of all individual Nodes = %d", totalHeight(root));
   return 0;
}


Input:

 

Output: 

Sum of heights of all Nodes = 8

 

Algorithm Complexity

Time Complexity 

We are traversing the tree in a preorder fashion, which takes O(n) time, and calculating the height of one node takes O(h) time where h is the height of the tree; hence time complexity is O(n*h).

Space Complexity

We are not using any extra space; the space complexity is O(1).

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

Efficient Approach

In the brute force approach, we have been using two functions. To optimize this, we can calculate the height and add them in the same recursive call.

Implementation in C++

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

// node
struct Node
{
   int data;
   struct Node *left;
   struct Node *right;
};

// new node
struct Node *newNode(int data)
{
   struct Node *Node = (struct Node *)
       malloc(sizeof(struct Node));
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;

   return (Node);
}

// function to calculate height in same recursive call
int totalHeight(struct Node *root, int &sum)
{
   if (root == NULL)
      return 0;

   int leftheight = totalHeight(root->left, sum);
   int rightheight = totalHeight(root->right, sum);
   int height = max(leftheight, rightheight) + 1;

   sum = sum + height;
   return height;
}

// Driver code
int main()
{
   struct Node *root = newNode(6);
   root->left = newNode(4);
   root->right = newNode(8);
   root->left->left = newNode(2);
   root->left->right = newNode(3);
   root->right->right = newNode(10);

   int sum = 0;
   totalHeight(root, sum);
   printf("Sum of heights of all individual Nodes = %d", sum);
   return 0;
}


Input: 

 

Output: 

Sum of heights of all Nodes = 10

 

Algorithm Complexity

Time complexity

Time complexity is O(n) as we are iterating the whole tree once and the tree consists of N nodes.
Space complexity

The space complexity is O(1) as we are not using any extra space.

Frequently Asked Questions

What are binary search trees used for?

A binary search tree is a data structure that allows for quick insertion, removal, and lookup of items while also providing an efficient way to iterate them in sorted order.

What is the difference between tree depth and height?

A node’s depth (or level) is its distance (number of edges) from the tree’s root node. The height is defined as the number of edges between the root node and the farthest leaf.

What is the degree of a node?

A node’s degree is determined by the number of connections it has to other nodes in the network. If you have 100 friends in a social network, the node that represents you has a degree of 100.

Conclusion

In this article, we have discussed the problem of finding the sum of heights of all individual nodes in a binary tree. We started with introducing the binary tree and height of a binary tree, problem statement, example, brute and optimized approach with their implementation in C++, and finally concluded with the time and space complexity of both the algorithm.

We hope you have gained a better understanding of the solution to this problem, and now it is your responsibility to solve it and try some new and different approaches. 

If you want to practice problems on binary trees, you can refer to these links:

  1. BST to sorted DLL
  2. Binary Tree Pruning
  3. Left View Of Binary Tree
  4. Symmetric Tree
  5. K Closest Points To Origin

 

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem 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 from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview 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 Coding.

Previous article
Diagonal Sum of a Binary Tree
Next article
Sum of subtree depths for every node of a given binary tree
Live masterclass