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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation for a simple binary tree

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

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int maxDiameter = 0;

int depth(TreeNode* node) {
    if (!node) return 0;
    int leftDepth = depth(node->left);
    int rightDepth = depth(node->right);
    maxDiameter = std::max(maxDiameter, leftDepth + rightDepth);
    return 1 + std::max(leftDepth, rightDepth);
}

int diameterOfBinaryTree(TreeNode* root) {
    maxDiameter = 0;
    depth(root);
    return maxDiameter;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    int result = diameterOfBinaryTree(root);
    std::cout << result << std::endl;
    return 0;
}

A 4

B 2

C 3

D 5

💡 Hint

The diameter is the longest path between any two nodes, which may pass through the root.

The longest path goes through nodes 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3, which has length 3 edges.

❓ Predict Output

intermediate

Diameter output for a skewed binary tree

What will be the output of the diameterOfBinaryTree function for the following skewed binary tree?

DSA C++

TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->right = new TreeNode(3);
root->right->right->right = new TreeNode(4);
int result = diameterOfBinaryTree(root);
std::cout << result << std::endl;

A 0

B 4

C 1

D 3

💡 Hint

In a skewed tree, the diameter is the length of the longest path which is the number of edges in the chain.

The tree is a straight line with 4 nodes, so the diameter is 3 edges.

🔧 Debug

advanced

Identify the error in diameter calculation code

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

DSA C++

int maxDiameter = 0;

int depth(TreeNode* node) {
    if (node == nullptr) return 0;
    int leftDepth = depth(node->left);
    int rightDepth = depth(node->right);
    maxDiameter = std::max(maxDiameter, leftDepth * rightDepth);
    return 1 + std::max(leftDepth, rightDepth);
}

int diameterOfBinaryTree(TreeNode* root) {
    maxDiameter = 0;
    depth(root);
    return maxDiameter;
}

A The diameter will be incorrect because it uses multiplication instead of addition

B Compilation error due to missing return statement

C Runtime error due to null pointer dereference

D No error, code works correctly

💡 Hint

Check how diameter is calculated from left and right depths.

Diameter is the sum of left and right depths, not their product. Using multiplication gives wrong results.

🧠 Conceptual

advanced

Understanding diameter definition in binary trees

Which of the following best describes the diameter of a binary tree?

A The number of edges on the longest path between any two nodes in the tree

B The height of the tree plus one

C The maximum depth of the left subtree

D The number of nodes on the longest path between any two nodes in the tree

💡 Hint

Diameter counts edges, not nodes.

Diameter is defined as the number of edges on the longest path between any two nodes.

🚀 Application

expert

Calculate diameter after modifying the tree

Given the initial tree below, what is the diameter after adding a new node as the left child of node 5? Initial tree: 1 ├─ 2 │ ├─ 4 │ └─ 5 └─ 3 Add node 6 as left child of node 5. What is the new diameter?

DSA C++

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->right->left = new TreeNode(6);
int result = diameterOfBinaryTree(root);
std::cout << result << std::endl;

A 5

B 4

C 3

D 6

💡 Hint

Consider the longest path after adding the new node 6.

The longest path is now 6 -> 5 -> 2 -> 1 -> 3, which has 4 edges.