Why Height of Binary Tree in DSA C++?

The Big Idea

What if you could instantly know the deepest level of any family or company tree without counting each step?

The Scenario

Imagine you have a family tree drawn on paper, and you want to know how many generations it has from the oldest ancestor to the youngest descendant.

Doing this by counting each branch manually is tiring and confusing, especially if the tree is big.

The Problem

Manually counting the height means checking every branch and level one by one.

This is slow and easy to make mistakes, especially if the tree has many branches or is unbalanced.

The Solution

Using the height of a binary tree concept, we can write a simple program that looks at each branch and finds the longest path from the root to a leaf automatically.

This saves time and avoids errors by letting the computer do the counting for us.

Before vs After

✗ Before

int countHeight(Node* root) {
  int height = 0;
  // Manually check each level and count
  // Very long and complex code
  return height;
}

✓ After

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

What It Enables

This lets us quickly find the depth of any tree, which helps in balancing trees, searching efficiently, and understanding data structure size.

Real Life Example

In a company's organizational chart, finding the height tells us how many management levels exist from the CEO down to the newest employee.

Key Takeaways

Manual counting is slow and error-prone for big trees.

Height calculation uses recursion to find the longest path easily.

This helps in many tree operations like balancing and searching.

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