Why Height of Binary Tree in DSA C?

The Big Idea

What if a simple program could instantly tell you the deepest level of any family or company tree?

The Scenario

Imagine you have a family tree drawn on paper. You want to know how many generations it has from the oldest ancestor to the youngest child. Counting each level by hand is tiring and easy to mess up.

The Problem

Manually counting the height means you must check every branch and remember the longest path. This is slow and you can forget or miscount branches, especially if the tree is big or uneven.

The Solution

Using the height of a binary tree concept, a simple program can check each branch automatically and find the longest path from the root to any leaf. It does this quickly and without mistakes.

Before vs After

✗ Before

int countHeight(Node* root) {
  // Manually check each branch and count
  // Very long and error-prone
}

✓ After

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

What It Enables

This lets you quickly find how deep a tree is, which helps in balancing trees, searching efficiently, and understanding data structure shape.

Real Life Example

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

Key Takeaways

Manual counting is slow and error-prone.

Height calculation uses recursion to find the longest path automatically.

Knowing height helps optimize and understand tree structures.

Practice

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

easy

A. 0

B. 1

C. 2

D. Undefined

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 A

4. Quick Check:

   Height of single node tree = 0 [OK]

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

Common Mistakes:

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

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

easy

A. void height(struct Node root);

B. int height(Node root);

C. int height(struct Node* root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, a tree node is usually passed as a pointer to struct Node.

2. Step 2: Check return type and parameter correctness

   The function returns an int (height) and takes a pointer to struct Node.

3. Final Answer:

   int height(struct Node* root); -> Option C

4. Quick Check:

   Correct signature uses pointer to struct Node [OK]

Hint: Use pointer to struct Node for tree parameters [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following code snippet calculating the height of this binary tree?

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

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

// Tree:
//     10
//    /  \
//   5    15
//        /
//       12

int main() {
  struct Node n12 = {12, NULL, NULL};
  struct Node n15 = {15, &n12, NULL};
  struct Node n5 = {5, NULL, NULL};
  struct Node n10 = {10, &n5, &n15};
  printf("%d", height(&n10));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace left subtree height

   Left subtree of root (10) has node 5 only, height = 1.

2. Step 2: Trace right subtree height

   Right subtree has nodes 15 and 12. Height is 2 (15 -> 12).

3. Step 3: Calculate total height

   Height = max(1, 2) + 1 (for root) = 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Height = 3 [OK]

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

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Off-by-one error in return statement

4. Identify the error in this height function and select the correct fix:

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

medium

A. Change base case return from -1 to 1

B. Change base case return from -1 to 0

C. Remove +1 from return statement

D. Change recursive calls to root->right and root->left swapped

Solution

1. Step 1: Understand base case meaning

   Base case returns height for empty tree. Returning -1 means height counts edges, not nodes.

2. Step 2: Fix base case for node count height

   To count nodes, base case should return 0 for NULL.

3. Final Answer:

   Change base case return from -1 to 0 -> Option B

4. Quick Check:

   Base case 0 for NULL node height [OK]

Hint: Base case for NULL should return 0 for node height [OK]

Common Mistakes:

• Returning -1 causes off-by-one height
• Removing +1 leads to wrong height
• Swapping left and right recursive calls unnecessary

5. Given a binary tree where each node has either 0 or 2 children, what is the height of a full binary tree with 7 nodes? Select the correct height.

hard

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Understand full binary tree properties

   A full binary tree with all nodes having 0 or 2 children has nodes count = 2^h - 1, where h is height.

2. Step 2: Calculate height from nodes count

   Given nodes = 7, solve 2^h - 1 = 7 -> 2^h = 8 -> h = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Full binary tree height for 7 nodes = 3 [OK]

Hint: Full tree nodes = 2^height - 1 formula [OK]

Common Mistakes:

• Confusing height with number of edges
• Using incomplete binary tree formula
• Miscounting nodes or height