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.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 2

B. Undefined

C. 1

D. 0

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Single node tree height = 0 [OK]

Hint: Height counts edges on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 0 for single node
• Confusing height with number of nodes
• Assuming height undefined for single node

2. Which of the following is the correct C++ function signature to calculate the height of a binary tree node named Node?

easy

A. int height(Node* root);

B. void height(Node root);

C. int height(Node root);

D. Node height(Node* root);

Solution

1. Step 1: Identify return type

   The height function returns an integer representing height, so return type is int.

2. Step 2: Identify parameter type

   Binary tree nodes are usually passed as pointers to avoid copying, so parameter is Node* root.

3. Final Answer:

   int height(Node* root); -> Option A

4. Quick Check:

   Return int, parameter Node pointer [OK]

Hint: Height returns int, takes pointer to Node [OK]

Common Mistakes:

• Using void return type
• Passing Node by value
• Returning Node instead of int

3. What is the output of the following C++ code snippet?

struct Node {
  int data;
  Node* left;
  Node* right;
};

int height(Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << height(&n3);
  return 0;
}

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Analyze tree structure

   Root n3 has two children n1 and n2, both leaves with height 1.

2. Step 2: Calculate height recursively

   Height of n1 and n2 is 1, so height of n3 = 1 + max(1,1) = 2.

3. Step 3: Confirm output

   The code prints height(&n3), which is 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   Height = 2 [OK]

Hint: Height = 1 + max(left, right) heights [OK]

Common Mistakes:

• Counting nodes instead of edges
• Returning 0 for non-empty tree
• Misreading tree structure

4. Identify the error in the following height function for a binary tree:

int height(Node* root) {
  if (root == nullptr) return -1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

medium

A. Base case should return 0, not -1

B. Function should return Node*, not int

C. Missing check for leaf nodes

D. Incorrect use of ternary operator

Solution

1. Step 1: Check base case return value

   Returning -1 for nullptr causes height to be off by one.

2. Step 2: Correct base case

   Base case should return 0 for empty tree to count height correctly.

3. Final Answer:

   Base case should return 0, not -1 -> Option A

4. Quick Check:

   Base case = 0 for empty tree [OK]

Hint: Base case for empty node returns 0 height [OK]

Common Mistakes:

• Returning -1 causes negative height
• Ignoring nullptr check
• Wrong return type

5. Given a binary tree where some nodes have only one child, what is the height of the tree below?

       10
      /  
     5    
      \   
       7  
        \
         9

hard

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace longest path from root to leaf

   Path is 10 -> 5 -> 7 -> 9, which has 4 nodes and 3 edges.

2. Step 2: Count edges on path

   Counting edges: 10-5 (1), 5-7 (2), 7-9 (3).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Count edges on longest root-to-leaf path [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring missing left child
• Assuming height is number of levels with both children