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.