Height of Binary Tree in DSA C++

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. We find it by checking the height of left and right subtrees and taking the bigger one plus one.

Analogy: Imagine a family tree where height means the number of generations from the oldest ancestor (root) down to the youngest descendant (leaf). The tallest branch shows the height.

    1
   / \
  2   3
 /   / \
4   5   6

Height is the longest path from 1 down to 4 or 5 or 6.

Dry Run Walkthrough

Input: Binary tree: root=1, left=2, right=3, left of 2=4, left of 3=5, right of 3=6

Goal: Find the height of this tree, which is the longest path from root to leaf

Step 1: Start at root node 1, find height of left subtree (node 2)

At node 1 -> exploring left subtree rooted at 2

Why: We need to find height of left subtree to compare with right subtree

Step 2: At node 2, find height of left subtree (node 4)

At node 2 -> exploring left subtree rooted at 4

Why: Continue down left subtree to find its height

Step 3: At node 4, no children, height is 1

Node 4 -> leaf node, height = 1

Why: Leaf node height is 1 by definition

Step 4: At node 2, right subtree is empty, height is 0; max height is max(1,0)+1=2

Node 2 -> left height=1, right height=0, total height=2

Why: Height at node 2 is one more than max height of its children

Step 5: At node 1, find height of right subtree (node 3)

At node 1 -> exploring right subtree rooted at 3

Why: Now find height of right subtree to compare

Step 6: At node 3, find height of left subtree (node 5)

At node 3 -> exploring left subtree rooted at 5

Why: Find height of left child of node 3

Step 7: At node 5, no children, height is 1

Node 5 -> leaf node, height = 1

Why: Leaf node height is 1

Step 8: At node 3, find height of right subtree (node 6)

At node 3 -> exploring right subtree rooted at 6

Why: Find height of right child of node 3

Step 9: At node 6, no children, height is 1

Node 6 -> leaf node, height = 1

Why: Leaf node height is 1

Step 10: At node 3, max height is max(1,1)+1=2

Node 3 -> left height=1, right height=1, total height=2

Why: Height at node 3 is one more than max height of its children

Step 11: At root node 1, max height is max(2,2)+1=3

Node 1 -> left height=2, right height=2, total height=3

Why: Height at root is one more than max height of left and right subtrees

Result:

Height of tree = 3

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
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; // base case: empty tree has height 0
    int leftHeight = height(root->left); // find height of left subtree
    int rightHeight = height(root->right); // find height of right subtree
    return max(leftHeight, rightHeight) + 1; // height is max of subtrees + 1 for root
}

int main() {
    // build tree from dry run example
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(6);

    cout << "Height of tree = " << height(root) << endl;
    return 0;
}

if (root == nullptr) return 0; // base case: empty tree has height 0

stop recursion at empty subtree, height 0

int leftHeight = height(root->left); // find height of left subtree

recursively find height of left subtree

int rightHeight = height(root->right); // find height of right subtree

recursively find height of right subtree

return max(leftHeight, rightHeight) + 1; // height is max of subtrees + 1 for root

height at current node is max child height plus one

Output

Height of tree = 3

Complexity Analysis

Time: O(n) because we visit every node once to compute height

Space: O(h) where h is tree height due to recursion call stack

vs Alternative: Iterative methods exist but recursion is simpler and intuitive for height calculation

Edge Cases

Empty tree (root is nullptr)

Returns height 0 immediately

DSA C++

if (root == nullptr) return 0; // base case: empty tree has height 0

Single node tree

Returns height 1 because root is leaf

DSA C++

return max(leftHeight, rightHeight) + 1; // height is max of subtrees + 1 for root

Skewed tree (all nodes only on one side)

Height equals number of nodes in the longest path

DSA C++

return max(leftHeight, rightHeight) + 1; // height is max of subtrees + 1 for root

When to Use This Pattern

When you need to find the longest path from root to leaf in a tree, use the height pattern by recursively checking subtree heights.

Common Mistakes

Mistake: Returning sum of left and right subtree heights instead of max
Fix: Return max(leftHeight, rightHeight) + 1 to get longest path, not sum

Mistake: Not handling nullptr base case causing runtime error
Fix: Add base case if (root == nullptr) return 0 to stop recursion

Summary

Calculates the longest path from root to any leaf node in a binary tree.

Use when you want to know the depth or height of a tree structure.

The height at any node is one plus the maximum height of its left and right children.