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

Time Complexity: Lowest Common Ancestor in Binary Tree

O(n)

Understanding Time Complexity

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

How does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* 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 recursion.

How Execution Grows With Input

As the tree grows, the function visits every node once to check for the target nodes.

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

Pattern observation: The number of steps grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the ancestor grows linearly with 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 check all nodes in the worst case to find both targets, so it visits every node once.

Interview Connect

Understanding this helps you explain how recursive tree searches work and why visiting all nodes is necessary in some cases.

Self-Check

"What if the tree was a binary search tree and you could use node values to guide the search? How would the time complexity change?"