Height of Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the height of this binary tree?

Consider the following binary tree structure and code to calculate its height. What will be the output?

DSA C

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:
//      1
//     / \
//    2   3
//   / 
//  4

int main() {
    struct Node n4 = {4, NULL, NULL};
    struct Node n2 = {2, &n4, NULL};
    struct Node n3 = {3, NULL, NULL};
    struct Node n1 = {1, &n2, &n3};
    int h = height(&n1);
    printf("%d\n", h);
    return 0;
}

A 2

B 3

C 4

D 1

💡 Hint

Height is the number of nodes on the longest path from root to a leaf.

The longest path is 1 -> 2 -> 4, which has 3 nodes, so height is 3.

❓ Predict Output

intermediate

What is the height of this skewed binary tree?

Given the following skewed binary tree and height function, what is the output?

DSA C

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:
// 1
//  \
//   2
//    \
//     3
//      \
//       4

int main() {
    struct Node n4 = {4, NULL, NULL};
    struct Node n3 = {3, NULL, &n4};
    struct Node n2 = {2, NULL, &n3};
    struct Node n1 = {1, NULL, &n2};
    int h = height(&n1);
    printf("%d\n", h);
    return 0;
}

A 4

B 2

C 3

D 1

💡 Hint

Height counts nodes along the longest path from root to leaf.

The tree is skewed to the right with nodes 1 -> 2 -> 3 -> 4, so height is 4.

🔧 Debug

advanced

What error occurs when running this height function?

Analyze the following code snippet. What error will it cause when executed?

DSA C

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 + 1 : rightHeight + 1;
}

int main() {
    struct Node* root = NULL;
    int h = height(root);
    printf("%d\n", h);
    return 0;
}

A 0

B Segmentation fault

C Compilation error

D Infinite recursion

💡 Hint

Check the base case when root is NULL.

The base case returns 0 when root is NULL, so height of empty tree is 0, no error occurs.

❓ Predict Output

advanced

What is the height of this full binary tree?

Given the full binary tree below, what will the height function output?

DSA C

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:
//       1
//      / \
//     2   3
//    / \ / \
//   4  5 6  7

int main() {
    struct Node n4 = {4, NULL, NULL};
    struct Node n5 = {5, NULL, NULL};
    struct Node n6 = {6, NULL, NULL};
    struct Node n7 = {7, NULL, NULL};
    struct Node n2 = {2, &n4, &n5};
    struct Node n3 = {3, &n6, &n7};
    struct Node n1 = {1, &n2, &n3};
    int h = height(&n1);
    printf("%d\n", h);
    return 0;
}

A 2

B 4

C 3

D 1

💡 Hint

Height counts nodes along the longest path from root to leaf.

The longest path is 1 -> 2 -> 4 (or 1 -> 3 -> 6), which has 3 nodes, so height is 3.

🚀 Application

expert

How many nodes are in a perfect binary tree of height 5?

A perfect binary tree is a full binary tree where all leaves are at the same level. Given the height is 5, how many nodes does it contain?

A 32

B 31

C 15

D 63

💡 Hint

Number of nodes in perfect binary tree = 2^height - 1

For height 5, nodes = 2^5 - 1 = 32 - 1 = 31. But height here counts nodes, so height 5 means levels 1 to 5, total nodes = 2^5 - 1 = 31.

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