Lowest Common Ancestor in Binary Tree in DSA Typescript - 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 taken?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  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 left and right subtrees 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 number of nodes in the tree grows, the function visits each node once to check for matches.

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

Pattern observation: The time 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 searches part of the tree, so it runs faster than visiting all nodes."

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

Interview Connect

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

Self-Check

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

Practice

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

easy

A. The root node of the binary tree

B. The lowest node that has both given nodes as descendants

C. The node with the highest value in the tree

D. The leaf node closest to the root

Solution

1. Step 1: Understand the definition of LCA

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

2. Step 2: Differentiate from other nodes

   It is not necessarily the root or the highest value node, but the shared ancestor closest to the two nodes.

3. Final Answer:

   The lowest node that has both given nodes as descendants -> Option B

4. Quick Check:

   LCA = lowest shared ancestor [OK]

Hint: LCA is the closest shared parent node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the node with highest value
• Assuming LCA must be a leaf node

2. Which of the following is the correct TypeScript function signature to find the LCA in a binary tree node structure?

easy

A. function findLCA(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode | null

B. function findLCA(root: TreeNode, p: number, q: number): number

C. function findLCA(root: TreeNode): TreeNode

D. function findLCA(p: TreeNode, q: TreeNode): TreeNode

Solution

1. Step 1: Analyze parameters needed for LCA

   To find LCA, we need the root of the tree and the two nodes (p and q) to find the ancestor for.

2. Step 2: Check return type

   The function should return the TreeNode that is the LCA or null if not found.

3. Final Answer:

   function findLCA(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode | null -> Option A

4. Quick Check:

   Correct signature includes root, p, q nodes and returns TreeNode or null [OK]

Hint: LCA function needs root and two nodes as input [OK]

Common Mistakes:

• Missing root parameter
• Using wrong parameter types like numbers instead of nodes
• Returning wrong type like number instead of TreeNode

3. Given the following TypeScript code for LCA, what will be the output if we call findLCA(root, node5, node1) where node5 and node1 are nodes with values 5 and 1 respectively?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

// Tree structure:
//       3
//      / \
//     5   1
//    / \ / \
//   6  2 0  8
//     / \
//    7   4

const root = new TreeNode(3);
const node5 = new TreeNode(5);
const node1 = new TreeNode(1);
root.left = node5;
root.right = node1;
// ... other nodes assigned similarly

const lca = findLCA(root, node5, node1);
console.log(lca?.val);

medium

A. 3

B. 5

C. 1

D. null

Solution

1. Step 1: Trace recursive calls for nodes 5 and 1

   Starting at root (3), left subtree contains node 5, right subtree contains node 1. Both left and right recursive calls return non-null nodes.

2. Step 2: Determine LCA based on recursive returns

   Since both left and right calls return nodes, current root (3) is the LCA.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA of 5 and 1 is 3 [OK]

Hint: If nodes are in different subtrees, LCA is root [OK]

Common Mistakes:

• Returning one of the nodes instead of their ancestor
• Confusing node values with node references
• Ignoring null checks in recursion

4. Identify the bug in the following TypeScript LCA function and select the correct fix:

function findLCA(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (root.val === p.val || root.val === q.val) return root;
  const left = findLCA(root.left, p, q);
  const right = findLCA(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

medium

A. Add a base case to return root when root is null

B. Replace logical OR with AND in return statement

C. Change comparisons to check node references, not values

D. Remove recursive calls to left and right subtrees

Solution

1. Step 1: Analyze node comparison logic

   The function compares node values (root.val === p.val), but nodes should be compared by reference to handle duplicates correctly.

2. Step 2: Correct the comparison to use reference equality

   Change to (root === p || root === q) to compare actual nodes, not just values.

3. Final Answer:

   Change comparisons to check node references, not values -> Option C

4. Quick Check:

   Node reference comparison fixes LCA correctness [OK]

Hint: Compare nodes by reference, not by value [OK]

Common Mistakes:

• Comparing node values instead of references
• Misusing logical operators in return
• Removing necessary recursion

5. You have a binary tree where nodes can have duplicate values. Which approach ensures correct Lowest Common Ancestor (LCA) identification for two given nodes p and q?

hard

A. Compare nodes by their values during recursion

B. Ignore duplicates and return the root as LCA

C. Return the node with the smaller value as LCA

D. Use node references (memory addresses) for comparison

Solution

1. Step 1: Understand the problem with duplicate values

   When values repeat, comparing nodes by value can lead to wrong LCA because multiple nodes share the same value.

2. Step 2: Use node references to uniquely identify nodes

   Comparing nodes by their references (actual objects) ensures the correct nodes are identified regardless of value duplicates.

3. Final Answer:

   Use node references (memory addresses) for comparison -> Option D

4. Quick Check:

   Reference comparison handles duplicates correctly [OK]

Hint: Use node references to handle duplicates safely [OK]

Common Mistakes:

• Comparing only node values
• Assuming smaller value node is LCA
• Ignoring duplicates in tree