Lowest Common Ancestor in Binary Tree in DSA Java - 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 time it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    return left != null ? 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 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The number of operations grows roughly in direct proportion to 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 searches part of the tree, so it runs faster than visiting all nodes."

[OK] Correct: The recursion explores both left and right subtrees fully in the worst case, so it visits all nodes.

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 and we used its ordering property? How would the time complexity change?"

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The node that is a child of both nodes

B. The deepest node that is an ancestor of both nodes

C. The node with the smallest value between the two nodes

D. The root node of the binary tree

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants (a node can be a descendant of itself).

2. Step 2: Clarify the options

   The deepest node that is an ancestor of both nodes correctly describes the LCA. The root node is not always the LCA, and the smallest value or child relationships do not define LCA.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option B

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the deepest shared ancestor node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is a child of given nodes

2. Which of the following is the correct Java method signature to find the LCA of two nodes in a binary tree?

easy

A. public void findLCA(TreeNode root, int n1, int n2)

B. public int findLCA(int root, TreeNode n1, TreeNode n2)

C. public TreeNode findLCA(int n1, int n2)

D. public TreeNode findLCA(TreeNode root, int n1, int n2)

Solution

1. Step 1: Analyze method parameters and return type

   The method should take the root node and two node values (or nodes) to find their LCA. It returns the TreeNode representing the LCA.

2. Step 2: Match with options

   public TreeNode findLCA(TreeNode root, int n1, int n2) matches this: it takes root and two integers, returns TreeNode. public int findLCA(int root, TreeNode n1, TreeNode n2) has wrong parameter types, C misses root, D returns void which is incorrect.

3. Final Answer:

   public TreeNode findLCA(TreeNode root, int n1, int n2) -> Option D

4. Quick Check:

   Correct signature includes root and returns TreeNode [OK]

Hint: LCA method needs root and two nodes, returns TreeNode [OK]

Common Mistakes:

• Omitting root parameter
• Wrong return type (void or int)
• Incorrect parameter order or types

3. Given the following binary tree and code snippet, what will be the output?

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4

TreeNode lca = findLCA(root, 5, 1);
System.out.println(lca.val);

medium

A. 3

B. 5

C. 1

D. 2

Solution

1. Step 1: Identify nodes 5 and 1 in the tree

   Node 5 is left child of root 3, node 1 is right child of root 3.

2. Step 2: Find their lowest common ancestor

   The lowest common ancestor of 5 and 1 is the root node 3, as it is the deepest node that has both as descendants.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: LCA of nodes on different sides is their root ancestor [OK]

Common Mistakes:

• Choosing one of the nodes instead of their ancestor
• Confusing child nodes as LCA
• Ignoring tree structure

4. The following Java method is intended to find the LCA of two nodes in a binary tree. What is the bug?

public TreeNode findLCA(TreeNode root, int n1, int n2) {
    if (root == null) return null;
    if (root.val == n1 || root.val == n2) return root;
    TreeNode left = findLCA(root.left, n1, n2);
    TreeNode right = findLCA(root.right, n1, n2);
    if (left != null && right != null) return root;
    if (left != null) return left;
    return right;
}

medium

A. It incorrectly returns root when both left and right are null

B. It returns null when both nodes are the same

C. It does not handle the case when one node is not present in the tree

D. It does not check for null root at the start

Solution

1. Step 1: Understand the method logic

   The method returns root if it matches either node, then recursively searches left and right subtrees. If both sides return non-null, root is LCA.

2. Step 2: Identify missing case

   The method assumes both nodes exist. If one node is missing, it may return the other node incorrectly as LCA without confirming presence of both.

3. Final Answer:

   It does not handle the case when one node is not present in the tree -> Option C

4. Quick Check:

   Missing node presence check causes incorrect LCA [OK]

Hint: Check both nodes exist before returning LCA [OK]

Common Mistakes:

• Ignoring missing node cases
• Assuming both nodes always exist
• Not validating subtree results properly

5. You have a binary tree where nodes can have duplicate values. How would you modify the standard LCA algorithm to correctly find the LCA of two nodes given their references (not values)?

hard

A. Use node references directly instead of comparing values during recursion

B. Use a hash map to store node values and find LCA by values

C. Ignore duplicates and return the first matching value node as LCA

D. Modify the tree to remove duplicates before finding LCA

Solution

1. Step 1: Understand the problem with duplicates

   When values are duplicated, comparing node values is unreliable to identify nodes uniquely.

2. Step 2: Use node references for comparison

   Instead of comparing values, compare the actual node references (memory addresses) to find exact nodes during recursion.

3. Step 3: Adjust algorithm accordingly

   Modify the LCA method to check if current node == target node references, not values.

4. Final Answer:

   Use node references directly instead of comparing values during recursion -> Option A

5. Quick Check:

   Use references, not values, for duplicates [OK]

Hint: Compare node references, not values, when duplicates exist [OK]

Common Mistakes:

• Comparing values instead of references
• Trying to remove duplicates unnecessarily
• Using value-based hash maps causing errors