Sum of heights of all individual nodes in a binary tree

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.

A 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;
}

You can also try this code with Online C++ Compiler

Run Code

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).