Lowest Common Ancestor in Binary Tree in DSA Javascript - Time & Space Complexity

Time Complexity: Lowest Common Ancestor in Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the lowest common ancestor changes as the tree grows.

How does the search through the tree affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ? left : right;
}
    

This code finds the lowest common ancestor of two nodes in a binary tree by searching both sides recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Each node is visited once during the search.

How Execution Grows With Input

As the number of nodes grows, the function checks each node once, so the work grows directly with the number of nodes.

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

Pattern observation: The time grows linearly with the number of nodes in the tree.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the ancestor grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function only visits part of the tree, so it runs faster than O(n)."

[OK] Correct: The function may need to visit every node in the worst case to find both targets, so it still takes time proportional to the whole tree.

Interview Connect

Understanding this helps you explain how recursive tree searches work and why visiting all nodes is sometimes necessary, a key skill in many coding challenges.

Self-Check

"What if the tree was a binary search tree? How would that change the time complexity?"