Height of Binary Tree in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the height of a binary tree?

The height of a binary tree is the number of edges on the longest path from the root node to a leaf node. It measures how tall the tree is.

beginner

How do you calculate the height of a binary tree recursively?

Calculate the height of the left subtree and the right subtree recursively, then take the maximum of these two heights and add 1 for the current node.

beginner

What is the height of an empty binary tree?

The height of an empty binary tree is defined as -1 because there are no nodes and no edges.

beginner

Why is the height of a single-node tree 0?

Because there are no edges from the root to any leaf (the root itself is the leaf), so the longest path has zero edges.

intermediate

What is the time complexity of computing the height of a binary tree?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the recursive height calculation.

What does the height of a binary tree represent?

A Number of edges in the longest path from root to leaf

B Number of nodes in the tree

C Number of leaf nodes

D Number of children of the root

The height is the count of edges on the longest path from the root node to any leaf node.

What is the height of an empty binary tree?

A 0

B Undefined

C -1

D 1

By definition, an empty tree has height -1 because it has no nodes or edges.

Which method is commonly used to find the height of a binary tree?

A Iterative level order traversal

B Counting leaf nodes

C Sorting nodes

D Recursive depth calculation

Recursion is used to calculate the height by checking left and right subtree heights.

If a binary tree has only one node, what is its height?

A 0

B 1

C -1

D 2

A single node tree has height 0 because there are no edges.

What is the time complexity to compute the height of a binary tree with n nodes?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Each node is visited once, so the time complexity is O(n).

Explain how to find the height of a binary tree using recursion.

Think about how you compare the heights of left and right children.

Describe the difference between the height of an empty tree and a single-node tree.

Consider how many edges exist in each case.

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