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 an empty binary tree?

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

beginner

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

The height is 0 because there are no edges from the root to any leaf (the root itself is a leaf).

intermediate

Explain the recursive approach to find the height of a binary tree.

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

intermediate

Why do we add 1 when calculating the height recursively?

We add 1 to count the current node itself, moving one level down the tree.

What is the height of a binary tree with only the root node?

A 0

B 1

C -1

D 2

A tree with only root has height 0 because there are no edges.

What is the height of an empty binary tree?

A 1

B 0

C -1

D Undefined

By definition, an empty tree has height -1.

Which of these best describes how to find the height of a binary tree?

A Find the longest path from root to leaf in edges

B Count the number of leaf nodes

C Count the number of nodes

D Find the shortest path from root to leaf

Height is the longest path from root to leaf measured in edges.

In the recursive height calculation, what do you do after finding left and right subtree heights?

A Add them

B Ignore them

C Take the minimum

D Take the maximum and add 1

We take the maximum height of the two subtrees and add 1 for the current node.

If a binary tree has height 3, how many edges are there on the longest path from root to leaf?

A 2

B 3

C 4

D 5

Height counts edges, so height 3 means 3 edges on the longest path.

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

Think about how you break down the problem into smaller parts.

Explain why the height of an empty binary tree is defined as -1.

Consider what height means and how it relates to edges.

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