Lowest Common Ancestor in Binary Tree in DSA Typescript - Build from Scratch

Lowest Common Ancestor in Binary Tree

📖 Scenario: You are working on a family tree application. You want to find the closest common ancestor of two family members in the tree.

🎯 Goal: Build a TypeScript program to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.

📋 What You'll Learn

Create a binary tree using a TreeNode class with val, left, and right properties.

Create a binary tree with the exact structure given.

Write a function lowestCommonAncestor that takes the root node and two nodes p and q and returns their lowest common ancestor node.

Print the value of the lowest common ancestor node.

💡 Why This Matters

🌍 Real World

Finding the lowest common ancestor is useful in family trees, organizational charts, and network routing to find shared connections.

💼 Career

Understanding tree traversal and recursion is important for software engineering roles involving data structures, algorithms, and system design.

1

Create the TreeNode class and the binary tree

Create a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create the binary tree with root node value 3, left child 5, right child 1, left child of 5 as 6, right child of 5 as 2, left child of 1 as 0, and right child of 1 as 8. The node 2 has left child 7 and right child 4.

DSA Typescript

// Create TreeNode class and build the binary tree as described
// Your code here

Hint

Think of each node as a person in the family tree. Use the TreeNode class to create each person and connect them as left and right children.

2

Select the two nodes to find their lowest common ancestor

Create two variables called p and q and assign them to the nodes with values 5 and 1 from the tree you created.

DSA Typescript

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

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

// Assign p to node with value 5 and q to node with value 1
// Your code here

Hint

Use the root variable and its left and right properties to assign p and q.

3

Write the function to find the lowest common ancestor

Write a function called lowestCommonAncestor that takes root, p, and q as parameters. Use recursion to find and return the lowest common ancestor node of p and q in the binary tree.

DSA Typescript

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

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 value 5
const q = root.right; // node with value 1

// Write the lowestCommonAncestor function below
// Your code here

Hint

Use recursion to check left and right subtrees. If both sides return a node, current root is the ancestor. If only one side returns a node, return that side.

4

Print the value of the lowest common ancestor

Use console.log to print the value of the node returned by lowestCommonAncestor(root, p, q).

DSA Typescript

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

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 value 5
const q = root.right; // node with value 1

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

// Print the value of the lowest common ancestor
// Your code here

Hint

Call the function with root, p, and q. Then print the val property of the returned node.

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