Lowest Common Ancestor in Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LCA for given nodes in a binary tree

What is the output of the following TypeScript code that finds the Lowest Common Ancestor (LCA) of nodes 5 and 1 in the binary tree?

DSA Typescript

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

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;
}

// Construct the tree
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const p = root.left; // Node with val 5
const q = root.right; // Node with val 1

const ancestor = lowestCommonAncestor(root, p, q);
console.log(ancestor ? ancestor.val : null);

A null

B 5

C 1

D 3

💡 Hint

Think about where nodes 5 and 1 meet first when traversing from the root.

The LCA of nodes 5 and 1 is the root node 3 because 5 is in the left subtree and 1 is in the right subtree. The function returns the first node where both nodes are found in different subtrees.

❓ Predict Output

intermediate

Output of LCA for nodes in same subtree

What is the output of the following TypeScript code that finds the Lowest Common Ancestor (LCA) of nodes 7 and 4 in the binary tree?

DSA Typescript

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

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;
}

// Construct the tree
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const p = root.left.right.left; // Node with val 7
const q = root.left.right.right; // Node with val 4

const ancestor = lowestCommonAncestor(root, p, q);
console.log(ancestor ? ancestor.val : null);

A 5

B 2

C 3

D 7

💡 Hint

Both nodes are in the right subtree of node 5.

Nodes 7 and 4 are both children of node 2, so their lowest common ancestor is node 2.

🔧 Debug

advanced

Identify the error in LCA function

What error will the following TypeScript code produce when trying to find the LCA of nodes 5 and 1?

DSA Typescript

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

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

// Construct the tree
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const p = root.left; // Node with val 5
const q = root.right; // Node with val 1

const ancestor = lowestCommonAncestor(root, p, q);
console.log(ancestor ? ancestor.val : null);

A No error, outputs 3

B TypeError: Cannot read property 'val' of null

C Outputs null

D Stack overflow due to infinite recursion

💡 Hint

Check how the function compares nodes using val property.

The function correctly checks for null and compares node values. It returns the root 3 as the LCA without error.

❓ Predict Output

advanced

Output when one node is ancestor of the other

What is the output of the following TypeScript code that finds the Lowest Common Ancestor (LCA) of nodes 5 and 4, where 5 is an ancestor of 4?

DSA Typescript

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

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;
}

// Construct the tree
const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const p = root.left; // Node with val 5
const q = root.left.right.right; // Node with val 4

const ancestor = lowestCommonAncestor(root, p, q);
console.log(ancestor ? ancestor.val : null);

A 3

B 4

C 5

D null

💡 Hint

If one node is ancestor of the other, the ancestor node is the LCA.

Since node 5 is an ancestor of node 4, the LCA is node 5 itself.

🧠 Conceptual

expert

Understanding LCA in a binary tree with no parent pointers

In a binary tree where nodes do not have parent pointers, which of the following statements about the Lowest Common Ancestor (LCA) algorithm is TRUE?

A The LCA algorithm must use recursion or a stack to explore subtrees from the root downwards.

B The LCA can be found by sorting the node values and picking the middle value.

C The LCA is always the root node of the tree regardless of input nodes.

D The LCA can be found by traversing from each node up to the root and comparing paths.

💡 Hint

Without parent pointers, you cannot move upwards from a node easily.

Without parent pointers, the algorithm must start from the root and explore subtrees recursively or with a stack to find the LCA.