Lowest Common Ancestor in Binary Tree in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

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

beginner

In the context of LCA, what does it mean for a node to be a descendant of itself?

It means that when checking if a node is a descendant of another, the node itself counts as its own descendant. So if one of the nodes is the ancestor of the other, the ancestor node is the LCA.

intermediate

What is the main idea behind the recursive approach to find LCA in a binary tree?

The recursive approach checks if the current node is one of the target nodes. Then it searches left and right subtrees. If both sides return a node, current node is LCA. If only one side returns a node, that side's node is passed up.

intermediate

Why do we return null when a subtree does not contain any of the target nodes in LCA algorithm?

Returning null means that subtree does not have either of the nodes we are looking for. This helps the parent call know which side contains the nodes and decide the LCA accordingly.

intermediate

What is the time complexity of the standard recursive LCA algorithm in a binary tree?

The time complexity is O(n), where n is the number of nodes in the tree, because in the worst case the algorithm visits every node once.

What does the Lowest Common Ancestor represent in a binary tree?

A The root node of the tree

B The node with the smallest value

C The deepest node that is ancestor to both given nodes

D The leaf node closest to the root

The LCA is the deepest node that has both nodes as descendants.

If one node is ancestor of the other, what is the LCA?

A No LCA exists

B The descendant node

C The root node

D The ancestor node

A node is considered a descendant of itself, so the ancestor node is the LCA.

In the recursive LCA algorithm, what does it mean if both left and right recursive calls return non-null?

A Only right subtree contains nodes

B Current node is the LCA

C Only left subtree contains nodes

D No LCA found

If both sides return nodes, current node is the lowest node connecting them.

What is returned by the recursive LCA function if neither subtree contains the target nodes?

A Null

B The current node

C One of the target nodes

D The root node

Null indicates no target nodes found in that subtree.

What is the time complexity of the recursive LCA algorithm in a binary tree with n nodes?

A O(n)

B O(log n)

C O(n^2)

D O(1)

The algorithm visits each node once, so time complexity is O(n).

Explain how the recursive algorithm finds the Lowest Common Ancestor in a binary tree.

Think about how recursion explores left and right children and combines results.

Describe a real-life analogy to understand the concept of Lowest Common Ancestor.

Imagine tracing back family members to find a shared ancestor.

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