How to Calculate the Height of a Binary Tree | Step-by-Step Guide

What Is the Height of a Binary Tree?

The height of a binary tree is the number of edges on the longest path from the root node (topmost node) to the farthest leaf node (a node with no children).

Example Binary Tree:

          1
       /     \
      2       3
     / \     / \
    4   5   6   7
         \
          8

• Height of left subtree: Nodes {2, 4, 5, 8} → Height = 3
• Height of right subtree: Nodes {3, 6, 7} → Height = 2
• Total Height: Max(3, 2) + 1 (root) = 4

Methods to Find the Height of a Binary Tree

1. Recursive Method

Algorithm:

1. If the tree is empty, return 0.
2. Recursively calculate the height of the left and right subtrees.
3. Take the maximum of the two heights and add 1 (to account for the root).

Code:

#include <iostream>
using namespace std;

// Definition of Node
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to calculate the height of the binary tree
int height_of_binary_tree(Node* root) {
    if (root == nullptr)
        return 0;
    
    int leftHeight = height_of_binary_tree(root->left);
    int rightHeight = height_of_binary_tree(root->right);
    
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->right->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "Height of the binary tree: " << height_of_binary_tree(root);
    return 0;
}

Output:

Height of the binary tree: 4

Complexity Analysis:

• Time Complexity: O(n) (Every node is visited once).
• Space Complexity: O(h) (Recursive stack space, where h is the height of the tree).

2. Iterative Approach (Using Level Order Traversal)

Algorithm:

1. Create a queue and enqueue the root node.
2. Initialize height = 0.
3. While the queue is not empty:
   • Determine the number of nodes at the current level (node_count).
   • Dequeue all nodes at this level and enqueue their children.
   • Increment height by 1 after processing each level.

Code:

#include <iostream>
#include <queue>
using namespace std;

// Definition of Node
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Function to calculate the height of the binary tree
int height_of_binary_tree(Node* root) {
    if (root == nullptr)
        return 0;
    
    queue<Node*> q;
    q.push(root);
    int height = 0;
    
    while (!q.empty()) {
        int node_count = q.size(); // Number of nodes at current level
        while (node_count > 0) {
            Node* current = q.front();
            q.pop();
            
            if (current->left)
                q.push(current->left);
            if (current->right)
                q.push(current->right);
            
            node_count--;
        }
        height++;
    }
    return height;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->right->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "Height of the binary tree: " << height_of_binary_tree(root);
    return 0;
}

Output:

Height of the binary tree: 4

Complexity Analysis:

• Time Complexity: O(n) (Every node is processed once).
• Space Complexity: O(w) (Maximum width of the tree, i.e., the number of nodes at the largest level).

Key Differences Between Recursive and Iterative Methods

Conclusion

Understanding the height of a binary tree is crucial in tree-based problems. While the recursive approach is simpler to implement, the iterative approach using level order traversal is efficient in managing stack space. Mastering both methods will strengthen your understanding of binary trees in data structures.

CLICK HERE TO KNOW MORE OUR PROGRAM!