How to Find the Height of a Binary Tree: Recursive and Iterative Methods Explained

How to Find the Height of a Binary Tree: Recursive and Iterative Methods Explained

Understanding how to calculate the height of a binary tree is a fundamental concept in data structures. The height of a binary tree is the number of edges on the longest path from the root node to a leaf node. This guide explores both recursive and iterative methods to calculate the height, complete with algorithms, code, and visual aids to simplify the process.

What Is the Height of a Binary Tree?

Height of a Binary TreeThe height of a binary tree is the distance from the root node (topmost node) to the farthest leaf node (node with no children).

Example Binary Tree:

markdown
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
  2. Iterative Method (Using Level Order Traversal)

Method 1: Recursive Approach

Algorithm:

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

Code:

cpp
#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:

css
Height of the binary tree: 4

Time Complexity:

  • O(n): Every node is visited once.

Space Complexity:

  • O(h): Recursive stack space, where h is the height of the tree.

Method 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:

cpp
#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:

css
Height of the binary tree: 4

Time Complexity:

  • O(n): Every node is processed once.

Space Complexity:

  • O(w): Maximum width of the tree (number of nodes at the largest level).

Key Differences Between Recursive and Iterative Methods

AspectRecursiveIterative
ApproachDivide-and-conquerLevel-order traversal
Space ComplexityO(h) (stack space)O(w) (queue space)
Ease of ImplementationSimpler to implementRequires explicit queue management
CLICK HERE TO KNOW MORE OUR PROGRAM!Height of a Binary Tree 
c