Diameter of Binary Tree in DSA Typescript - Time & Space Complexity

Time Complexity: Diameter of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the diameter of a binary tree.

The question is: how does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function diameterOfBinaryTree(root: TreeNode | null): number {
  let diameter = 0;
  function depth(node: TreeNode | null): number {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
  }
  depth(root);
  return diameter;
}
    

This code finds the longest path between any two nodes in a binary tree by calculating depths recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to visit each node once.
• How many times: Each node is visited exactly one time.

How Execution Grows With Input

As the tree grows, the function visits every node once to calculate depths.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The number of operations grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the diameter grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function calls depth multiple times per node, so it must be more than linear."

[OK] Correct: Each node is visited once because the recursive calls do not repeat work; results are combined on the way back.

Interview Connect

Understanding this helps you explain how recursion can efficiently solve tree problems by visiting nodes once.

Self-Check

"What if we changed the code to calculate depth separately for left and right subtrees multiple times? How would the time complexity change?"