Diameter of Binary Tree in DSA C++ - Time & Space Complexity

Time Complexity: Diameter of Binary Tree

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find the diameter of a binary tree changes as the tree grows.

The question is: how does the work increase when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int height(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + max(leftHeight, rightHeight);
}

int diameter(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    int leftDiameter = diameter(root->left);
    int rightDiameter = diameter(root->right);
    return max(leftHeight + rightHeight, max(leftDiameter, rightDiameter));
}
    

This code finds the diameter by computing heights and diameters of subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to height and diameter functions.
• How many times: For each node, height is called multiple times leading to repeated work.

How Execution Grows With Input

As the number of nodes (n) increases, the height function is called many times for the same nodes, causing repeated work.

Input Size (n)	Approx. Operations
10	~100 calls
100	~10,000 calls
1000	~1,000,000 calls

Pattern observation: The work grows roughly with the square of the number of nodes because height is recomputed many times.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the number of nodes in the tree.

Common Mistake

[X] Wrong: "The diameter function runs in linear time because it visits each node once."

[OK] Correct: The height function is called repeatedly for the same nodes, causing extra work that adds up to quadratic time.

Interview Connect

Understanding this helps you explain why naive recursive solutions can be slow and how to improve them, a key skill in interviews.

Self-Check

"What if we compute height once for each node and store it? How would the time complexity change?"