Lowest Common Ancestor in Binary Tree in DSA Go - 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 grows as the tree gets bigger.

How does the search through the tree affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return 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 checked once during the recursion.

How Execution Grows With Input

As the tree grows, the function visits every node once to find the answer.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the lowest common ancestor grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function only checks a small 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 must check the whole tree.

Interview Connect

Understanding this linear time complexity helps you explain why this approach is efficient and expected when working with binary trees.

Self-Check

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