# Sum of heights of all individual nodes in a binary tree

Given a binary tree, find sum of heights all individual Nodes in the tree.

Example:

```For this tree:
1). Height of Node 1 - 3
2). Height of Node 2 - 2
3). Height of Node 3 - 1
4). Height of Node 4 - 1
5). Height of Node 5 - 1

Adding all of them = 8
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Prerequisites :-
Height of binary tree

Simple Solution :

We get the height of all individual Nodes by parsing the tree in any of the following methods i.e. Inorder, postorder, preorder(I performed inorder tree traversal) and getting their heights using getHeight function which checks both left and right subtree and returns the maximum of them. Finally we add up all the individual heights.

## C++

 `// CPP program to find sum of heights of all ` `// nodes in a binary tree ` `#include ` `#include ` ` `  `/* A binary tree Node has data, pointer to ` `    ``left child and a pointer to right child */` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `/* Compute the "maxHeight" of a particular Node*/` `int` `getHeight(``struct` `Node* Node) ` `{ ` `    ``if` `(Node == NULL) ` `        ``return` `0; ` `    ``else` `{ ` `        ``/* compute the height of each subtree */` `        ``int` `lHeight = getHeight(Node->left); ` `        ``int` `rHeight = getHeight(Node->right); ` ` `  `        ``/* use the larger one */` `        ``if` `(lHeight > rHeight) ` `            ``return` `(lHeight + 1); ` `        ``else` `            ``return` `(rHeight + 1); ` `    ``} ` `} ` ` `  `/* Helper function that allocates a new Node with the ` `   ``given data and NULL left and right pointers. */` `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 sum of heights of individual Nodes ` `   ``Uses Inorder traversal */` `int` `getTotalHeight(``struct` `Node* root) ` `{ ` `    ``if` `(root == NULL) ` `        ``return` `0; ` ` `  `    ``return` `getTotalHeight(root->left) +  ` `           ``getHeight(root) +  ` `           ``getTotalHeight(root->right); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``struct` `Node* root = newNode(1); ` ` `  `    ``root->left = newNode(2); ` `    ``root->right = newNode(3); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(5); ` `    ``printf``(``"Sum of heights of all Nodes = %d"``,     ` `                        ``getTotalHeight(root)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find sum of heights of all  ` `// nodes in a binary tree  ` `class` `GfG {  ` ` `  `/* A binary tree Node has data, pointer to  ` `    ``left child and a pointer to right child */` `static` `class` `Node {  ` `    ``int` `data;  ` `    ``Node left;  ` `    ``Node right;  ` `}  ` ` `  `/* Compute the "maxHeight" of a particular Node*/` `static` `int` `getHeight(Node Node)  ` `{  ` `    ``if` `(Node == ``null``)  ` `        ``return` `0``;  ` `    ``else` `{  ` `        ``/* compute the height of each subtree */` `        ``int` `lHeight = getHeight(Node.left);  ` `        ``int` `rHeight = getHeight(Node.right);  ` ` `  `        ``/* use the larger one */` `        ``if` `(lHeight > rHeight)  ` `            ``return` `(lHeight + ``1``);  ` `        ``else` `            ``return` `(rHeight + ``1``);  ` `    ``}  ` `}  ` ` `  `/* Helper function that allocates a new Node with the  ` `given data and NULL left and right pointers. */` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node Node = ``new` `Node();  ` `    ``Node.data = data;  ` `    ``Node.left = ``null``;  ` `    ``Node.right = ``null``;  ` ` `  `    ``return` `(Node);  ` `}  ` ` `  `/* Function to sum of heights of individual Nodes  ` `Uses Inorder traversal */` `static` `int` `getTotalHeight( Node root)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return` `0``;  ` ` `  `    ``return` `getTotalHeight(root.left) + getHeight(root) + getTotalHeight(root.right);  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``Node root = newNode(``1``);  ` ` `  `    ``root.left = newNode(``2``);  ` `    ``root.right = newNode(``3``);  ` `    ``root.left.left = newNode(``4``);  ` `    ``root.left.right = newNode(``5``);  ` `    ``System.out.println(``"Sum of heights of all Nodes = "` `+ getTotalHeight(root));  ` `} ` `}  `

## Python3

 `# Python3 program to find sum of heights ` `# of all nodes in a binary tree  ` ` `  `# Helper class that allocates a new Node ` `# with the given data and None left and  ` `# right pointers.  ` `class` `newNode: ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data  ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` ` `  `# Compute the "maxHeight" of a  ` `# particular Node ` `def` `getHeight(Node): ` `    ``if` `(Node ``=``=` `None``):  ` `        ``return` `0` `    ``else``: ` `         `  `        ``# compute the height of each subtree  ` `        ``lHeight ``=` `getHeight(Node.left)  ` `        ``rHeight ``=` `getHeight(Node.right) ` ` `  `        ``# use the larger one  ` `        ``if` `(lHeight > rHeight):  ` `            ``return` `(lHeight ``+` `1``)  ` `        ``else``: ` `            ``return` `(rHeight ``+` `1``)  ` `             `  `# Function to sum of heights of  ` `# individual Nodes Uses Inorder traversal  ` `def` `getTotalHeight(root): ` `    ``if` `(root ``=``=` `None``): ` `        ``return` `0` ` `  `    ``return` `(getTotalHeight(root.left) ``+`  `            ``getHeight(root) ``+`  `            ``getTotalHeight(root.right)) ` ` `  `# Driver code  ` `if` `__name__ ``=``=` `'__main__'``: ` `    ``root ``=` `newNode(``1``)  ` ` `  `    ``root.left ``=` `newNode(``2``)  ` `    ``root.right ``=` `newNode(``3``)  ` `    ``root.left.left ``=` `newNode(``4``)  ` `    ``root.left.right ``=` `newNode(``5``)  ` `print``(``"Sum of heights of all Nodes ="``, ` `                 ``getTotalHeight(root)) ` ` `  `# This code is contributed by PranchalK `

## C#

 `// C# program to find sum of heights of all  ` `// nodes in a binary tree  ` `using` `System; ` ` `  `class` `GfG  ` `{  ` ` `  `/* A binary tree Node has data, pointer to  ` `    ``left child and a pointer to right child */` `public` `class` `Node  ` `{  ` `    ``public` `int` `data;  ` `    ``public` `Node left;  ` `    ``public` `Node right;  ` `}  ` ` `  `/* Compute the "maxHeight" of a particular Node*/` `static` `int` `getHeight(Node Node)  ` `{  ` `    ``if` `(Node == ``null``)  ` `        ``return` `0;  ` `    ``else`  `    ``{  ` `        ``/* compute the height of each subtree */` `        ``int` `lHeight = getHeight(Node.left);  ` `        ``int` `rHeight = getHeight(Node.right);  ` ` `  `        ``/* use the larger one */` `        ``if` `(lHeight > rHeight)  ` `            ``return` `(lHeight + 1);  ` `        ``else` `            ``return` `(rHeight + 1);  ` `    ``}  ` `}  ` ` `  `/* Helper function that allocates a new Node with the  ` `given data and NULL left and right pointers. */` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node Node = ``new` `Node();  ` `    ``Node.data = data;  ` `    ``Node.left = ``null``;  ` `    ``Node.right = ``null``;  ` ` `  `    ``return` `(Node);  ` `}  ` ` `  `/* Function to sum of heights of individual Nodes  ` `Uses Inorder traversal */` `static` `int` `getTotalHeight( Node root)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return` `0;  ` ` `  `    ``return` `getTotalHeight(root.left) +  ` `                    ``getHeight(root) +  ` `                    ``getTotalHeight(root.right);  ` `}  ` ` `  `// Driver code  ` `public` `static` `void` `Main(String []args)  ` `{  ` `    ``Node root = newNode(1);  ` ` `  `    ``root.left = newNode(2);  ` `    ``root.right = newNode(3);  ` `    ``root.left.left = newNode(4);  ` `    ``root.left.right = newNode(5);  ` `    ``Console.Write(``"Sum of heights of all Nodes = "` `+ getTotalHeight(root));  ` `}  ` `} ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```Sum of heights of all Nodes = 8
```

Time Complexity : O(nh) where n is total number of nodes and h is height of binary tree.

Efficient Solution :

The idea is to compute heights and sum in same recursive call.

 `// CPP program to find sum of heights of all ` `// nodes in a binary tree ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree Node has data, pointer to ` `    ``left child and a pointer to right child */` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node* left; ` `    ``struct` `Node* right; ` `}; ` ` `  `/* Helper function that allocates a new Node with the ` `   ``given data and NULL left and right pointers. */` `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 sum of heights of individual Nodes ` `   ``Uses Inorder traversal */` `int` `getTotalHeightUtil(``struct` `Node* root, ``int` `&sum) ` `{ ` `    ``if` `(root == NULL) ` `        ``return` `0; ` ` `  `    ``int` `lh = getTotalHeightUtil(root->left, sum); ` `    ``int` `rh = getTotalHeightUtil(root->right, sum); ` `    ``int` `h = max(lh, rh) + 1; ` ` `  `    ``sum = sum + h; ` `    ``return` `h; ` `} ` ` `  `int` `getTotalHeight(Node *root) ` `{ ` `    ``int` `sum = 0; ` `    ``getTotalHeightUtil(root, sum); ` `    ``return` `sum;  ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``struct` `Node* root = newNode(1); ` ` `  `    ``root->left = newNode(2); ` `    ``root->right = newNode(3); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(5); ` `    ``printf``(``"Sum of heights of all Nodes = %d"``,     ` `                        ``getTotalHeight(root)); ` `    ``return` `0; ` `} `

Output:

```Sum of heights of all Nodes = 8
```

Time Complexity : O(nh) where n is total number of nodes and h is height of binary tree.

Tree Tree