Height of a Binary Tree: Recursive and Iterative Methods

Binary tree height, defined as the number of nodes on the longest root-to-leaf path, is one of the most consistently tested tree properties in placement coding rounds.

Two methods solve it: a recursive divide-and-conquer approach and an iterative BFS approach. They have the same time complexity but different space trade-offs, and knowing when each applies is exactly the follow-up interviewers ask after you write the first one.

What Is the Height of a Binary Tree?

A binary tree is a data structure where each node has at most two children: a left child and a right child. The height of the tree is the number of nodes on the longest path from the root to any leaf.

Two conventions exist:

• Node-count (used in this article): an empty tree has height 0; a tree with only a root has height 1. Each level of the tree adds 1.
• Edge-count: an empty tree has height -1 or 0 (definitions vary); a tree with only a root has height 0. The result is always one less than the node-count.

The code in this article uses node-count. Confirm the convention with your interviewer before writing code.

Consider this 8-node tree:

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

The longest path is 1 → 2 → 5 → 8. That is four nodes. Height = 4.

Recursive Method

Each node contributes exactly 1 to the height of the path that passes through it. The height of any subtree is 1 plus the height of its taller child subtree. An empty subtree contributes nothing.

Algorithm

• If root is nullptr, return 0.
• Recursively compute leftHeight = height(root->left).
• Recursively compute rightHeight = height(root->right).
• Return max(leftHeight, rightHeight) + 1.

C++ Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int height(Node* root) {
    if (root == nullptr) return 0;
    int leftH  = height(root->left);
    int rightH = height(root->right);
    return max(leftH, rightH) + 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: " << height(root);  // Output: 4
    return 0;
}

How the Recursion Works

Tracing the example tree bottom-up:

• height(8) = max(0, 0) + 1 = 1
• height(4) = max(0, 0) + 1 = 1
• height(6) = max(0, 0) + 1 = 1
• height(7) = max(0, 0) + 1 = 1
• height(5) = max(0, 1) + 1 = 2 (right child 8 has height 1)
• height(2) = max(1, 2) + 1 = 3 (left child 4 height 1, right child 5 height 2)
• height(3) = max(1, 1) + 1 = 2
• height(1) = max(3, 2) + 1 = 4

Complexity

• Time: O(n). Every node is visited exactly once.
• Space: O(h), where h is the tree height. Each active recursive call occupies one frame on the call stack. For a balanced tree h = O(log n); for a fully skewed tree h = O(n).

The space complexity breakdown covers why O(log n) stack depth for balanced trees differs from O(n) for skewed ones, with worked derivations.

Iterative Method (BFS / Level-Order Traversal)

Height equals the number of levels in the tree. BFS visits all nodes at depth d before any node at depth d+1, so a counter that increments once per level gives the height directly.

Algorithm

• If root is nullptr, return 0.
• Create a queue. Push root. Set height = 0.
• While the queue is not empty:
  • Record nodeCount = queue.size() (nodes in the current level).
  • Dequeue each of those nodeCount nodes; enqueue their non-null children.
  • Increment height by 1.
• Return height.

C++ Implementation

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

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int heightBFS(Node* root) {
    if (root == nullptr) return 0;

    queue<Node*> q;
    q.push(root);
    int height = 0;

    while (!q.empty()) {
        int nodeCount = q.size();
        while (nodeCount--) {
            Node* curr = q.front();
            q.pop();
            if (curr->left)  q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        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: " << heightBFS(root);  // Output: 4
    return 0;
}

The std::queue from the C++ Standard Library manages the BFS frontier. The outer while loop handles one complete level per iteration; the inner while drains all nodes at that level before the counter increments.

How BFS Counts Levels

On the example tree:

• Level 1: queue = 1. Enqueue children 2 and 3. Height = 1.
• Level 2: queue = 3. Enqueue children 4, 5, 6, 7. Height = 2.
• Level 3: queue = 7. Enqueue child 8. Height = 3.
• Level 4: queue = 8. No children to enqueue. Height = 4.
• Queue empty. Return 4.

Complexity

• Time: O(n). Every node is enqueued and dequeued exactly once.
• Space: O(w), where w is the maximum width of the tree — the number of nodes at the widest level. For a complete binary tree the widest level holds roughly n/2 nodes.

Recursive vs Iterative: When to Use Which

Aspect	Recursive	Iterative (BFS)
Space used	O(h) on call stack	O(w) in heap queue
Balanced tree space	O(log n)	O(n/2)
Skewed tree space	O(n) — stack risk	O(1) — only one node queued at a time
Code lines	~5 lines	~15 lines
Interview clarity	High	Moderate

When to pick iterative

If the input tree may be heavily skewed (a BST built by inserting a sorted array, for example), the recursive method’s call stack grows as deep as the tree. At large depths this overflows the stack. BFS avoids this by storing nodes in a heap-allocated queue, which has a much larger capacity than the call stack.

Practising array-based problems like finding all symmetric pairs alongside tree problems helps build the mental model for when to reach for an explicit data structure versus letting the call stack do the work.

When to pick recursive

For balanced trees, interviews, and any context where code brevity matters. The recursive version is five lines, obviously correct, and easy to explain out loud while the interviewer watches. Most placement coding rounds don’t include test cases designed specifically to overflow the recursion stack.

The iterative approach is worth having in your toolkit alongside other traversal-based problems like the equilibrium index, where understanding which data structures to reach for separates a complete answer from a partial one.

From Tree BFS to AI Graph Search

The BFS frontier pattern in the iterative method drains all nodes at the current level into a queue before expanding to the next level. That same logic powers breadth-first graph search algorithms in AI planning systems, shortest-path problems in robotics navigation, and state-space search in game AI.

The O(w) queue reasoning from the iterative method here translates directly once you move from trees to general graphs. TinkerLLM is a way to take that intuition into applied contexts for ₹299, without committing to a 9-month programme upfront.