Write an efficient algorithm to compute the height of binary tree. The height or depth of a tree is number of edges or nodes on longest path from root node to leaf node.

The program should consider number of nodes in the longest path. For example, height of an empty tree is 0 and height of tree with only one node is 1.

The idea is to traverse the tree in post-order fashion and calculate the height of left and right subtree. The height of the subtree rooted at any node will be equal to maximum height of its left and right subtree plus one. We recursively apply this property to all tree nodes in bottom-up manner (post-order fashion) and return maximum height of the subtree rooted at that node.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 |
// Recursive function to calculate height of given binary tree int height(Node* root) { // Base case: empty tree has height 0 if (root == nullptr) return 0; // recurse for left and right subtree and consider maximum depth return max(height(root->left), height(root->right)) + 1; } |

#### Iterative solution –

In iterative version, we perform level order traversal of the tree. The height of the tree is equal to number of levels in the tree.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Iterative function to calculate height of given binary tree // by doing level order traversal of the tree int height(Node *root) { // empty tree has height 0 if (root == nullptr) return 0; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); Node* front = nullptr; int height = 0; // run till queue is not empty while (!queue.empty()) { // calculate number of nodes in current level int size = queue.size(); // process every node of current level and enqueue their // non-empty left and right child to queue while (size--) { front = queue.front(); queue.pop_front(); if (front->left) queue.push_back(front->left); if (front->right) queue.push_back(front->right); } // increment height by 1 for each level height++; } return height; } |

The time complexity of both recursive and iterative solution is O(n).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

<3