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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of height calculation on a simple binary tree

What is the output of the following C++ code that calculates the height of a binary tree?

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    int h = height(root);
    std::cout << h << std::endl;
    return 0;
}

A 3

B 2

C 4

D 5

💡 Hint

Count the longest path from root to leaf node.

The height is the number of nodes on the longest path from the root to a leaf. Here, the longest path is 1 -> 2 -> 4 or 1 -> 2 -> 5, which has 3 nodes.

🧠 Conceptual

intermediate

Understanding height of an empty tree

What is the height of an empty binary tree (where the root is nullptr)?

A -1

B 1

C 0

D Undefined

💡 Hint

Think about the base case in the height function.

By definition, the height of an empty tree is 0 because there are no nodes.

❓ Predict Output

advanced

Height of an unbalanced binary tree

What is the output of the following code that calculates the height of an unbalanced binary tree?

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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* root = new Node(10);
    root->left = new Node(20);
    root->left->left = new Node(40);
    root->left->left->left = new Node(80);
    root->right = new Node(30);
    int h = height(root);
    std::cout << h << std::endl;
    return 0;
}

A 3

B 4

C 5

D 2

💡 Hint

Check the longest path from root to leaf on the left side.

The longest path is 10 -> 20 -> 40 -> 80, which has 4 nodes, so height is 4.

🔧 Debug

advanced

Identify the error in height calculation code

What error will the following code produce when calculating the height of a binary tree?

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    std::cout << height(root) << std::endl;
    return 0;
}

A Runtime error due to null pointer dereference

B Syntax error due to missing semicolon

C Outputs zero always

D The code outputs the minimum height instead of maximum height

💡 Hint

Check the comparison operator used to select height.

The code uses < instead of > to select between leftHeight and rightHeight, so it returns the minimum height path plus one, not the maximum.

🚀 Application

expert

Height of a binary tree after inserting nodes in a specific order

Given an initially empty binary tree, nodes are inserted in this order: 15, 10, 20, 8, 12, 17, 25, 6. What is the height of the tree after all insertions?

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

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* root = nullptr;
    int values[] = {15, 10, 20, 8, 12, 17, 25, 6};
    for (int v : values) {
        root = insert(root, v);
    }
    std::cout << height(root) << std::endl;
    return 0;
}

A 4

B 3

C 5

D 6

💡 Hint

Draw the tree after insertions and count the longest path.

After inserting nodes, the longest path is 15 -> 10 -> 8 -> 6, which has 4 nodes, so height is 4.

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