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

Lowest Common Ancestor in Binary Tree

📖 Scenario: Imagine a family tree where each person has two parents at most. We want to find the closest common ancestor of two family members.

🎯 Goal: Build a simple binary tree and write a function to find the lowest common ancestor (LCA) of two given nodes.

📋 What You'll Learn

Create a binary tree with specific nodes

Add a helper function to find nodes by value

Write a function to find the lowest common ancestor of two nodes

Print the value of the lowest common ancestor

💡 Why This Matters

🌍 Real World

Finding common ancestors is useful in family trees, organizational charts, and file systems to understand relationships.

💼 Career

Understanding tree traversal and ancestor queries is important for software engineers working with hierarchical data and algorithms.

1

Create the Binary Tree Nodes

Create a binary tree by defining a class called TreeNode with a constructor that takes val, left, and right. Then create nodes with values 3, 5, 1, 6, 2, 7, 4, 0, and 8 and link them to form this tree:

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

DSA Javascript

// Define TreeNode class and create nodes with values 3, 5, 1, 6, 2, 7, 4, 0, 8
// Link nodes to form the tree structure
// Your code here

Hint

Start by defining the TreeNode class. Then create each node from bottom to top, linking children to parents.

2

Add a Function to Find a Node by Value

Add a function called findNode that takes root and val and returns the node with that value by searching the tree recursively.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const node7 = new TreeNode(7);
const node4 = new TreeNode(4);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node7, node4);
const node5 = new TreeNode(5, node6, node2);
const node0 = new TreeNode(0);
const node8 = new TreeNode(8);
const node1 = new TreeNode(1, node0, node8);
const root = new TreeNode(3, node5, node1);

// Write function findNode(root, val) to return the node with value val
// Your code here

Hint

Use recursion to check if the current node matches val. If not, search left and right subtrees.

3

Write the Lowest Common Ancestor Function

Write a function called lowestCommonAncestor that takes root, p, and q (nodes) and returns their lowest common ancestor node using recursion.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const node7 = new TreeNode(7);
const node4 = new TreeNode(4);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node7, node4);
const node5 = new TreeNode(5, node6, node2);
const node0 = new TreeNode(0);
const node8 = new TreeNode(8);
const node1 = new TreeNode(1, node0, node8);
const root = new TreeNode(3, node5, node1);

function findNode(root, val) {
  if (root === null) return null;
  if (root.val === val) return root;
  return findNode(root.left, val) || findNode(root.right, val);
}

// Write function lowestCommonAncestor(root, p, q) to find LCA
// Your code here

Hint

Use recursion to check left and right subtrees. If both sides return a node, current root is LCA. Otherwise, return the non-null side.

4

Find and Print the Lowest Common Ancestor

Use findNode to get nodes p with value 5 and q with value 1. Then call lowestCommonAncestor(root, p, q) and print the val of the result.

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const node7 = new TreeNode(7);
const node4 = new TreeNode(4);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node7, node4);
const node5 = new TreeNode(5, node6, node2);
const node0 = new TreeNode(0);
const node8 = new TreeNode(8);
const node1 = new TreeNode(1, node0, node8);
const root = new TreeNode(3, node5, node1);

function findNode(root, val) {
  if (root === null) return null;
  if (root.val === val) return root;
  return findNode(root.left, val) || findNode(root.right, val);
}

function lowestCommonAncestor(root, p, q) {
  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;
}

// Find nodes with values 5 and 1
// Call lowestCommonAncestor and print the val
// Your code here

Hint

Use findNode to get nodes for 5 and 1. Then call lowestCommonAncestor with these nodes and print the val of the result.

Practice

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

easy

A. The node that appears first in an inorder traversal

B. The root node of the binary tree

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

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

Solution

1. Step 1: Understand ancestor concept

   An ancestor of a node is any node on the path from the root to that node.

2. Step 2: Define lowest common ancestor

   The lowest common ancestor is the deepest node that is an ancestor of both given nodes.

3. Final Answer:

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

4. Quick Check:

   LCA = deepest common ancestor [OK]

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

Common Mistakes:

• Confusing LCA with root node
• Choosing node with smallest value
• Selecting node based on traversal order

2. Which of the following is the correct base case condition in a recursive function to find LCA in a binary tree?

easy

A. if (root.right == null) return root;

B. if (root.left == null) return root;

C. if (root.value == null) return root;

D. if (root == null) return null;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null, it means we've reached the end of a path without finding the target nodes.

2. Step 2: Correct base case condition

   Return null to indicate no ancestor found in this path.

3. Final Answer:

   if (root == null) return null; -> Option D

4. Quick Check:

   Base case returns null on null node [OK]

Hint: Return null when node is null [OK]

Common Mistakes:

• Returning root when left or right child is null
• Checking root.value == null which is invalid
• Missing base case leading to infinite recursion

3. Consider the following binary tree and code snippet to find LCA of nodes 5 and 1:

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

function findLCA(root, p, q) {
  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;
}

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

What will be printed?

medium

A. 5

B. 3

C. 1

D. null

Solution

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

   Both nodes 5 and 1 are children of root 3, so recursion finds them in left and right subtrees respectively.

2. Step 2: Determine LCA based on recursion

   Since left and right recursive calls return non-null (nodes 5 and 1), the current root 3 is the LCA.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   LCA of 5 and 1 is 3 [OK]

Hint: If both sides return nodes, root is LCA [OK]

Common Mistakes:

• Returning one of the nodes instead of root
• Confusing node values with LCA
• Ignoring both left and right recursive results

4. The following code attempts to find the LCA but has a bug. What is the error?

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

medium

A. It returns left child even if right child is also non-null

B. It does not check if root is null

C. It returns root instead of null when no nodes found

D. It does not handle the case when p or q is missing

Solution

1. Step 1: Analyze return conditions after recursion

   The code returns left if left is non-null without checking right, missing the case when both are non-null.

2. Step 2: Identify missing combined check

   It should return root if both left and right are non-null, indicating LCA found at current root.

3. Final Answer:

   It returns left child even if right child is also non-null -> Option A

4. Quick Check:

   Must check both sides before returning [OK]

Hint: Check both left and right before returning root [OK]

Common Mistakes:

• Returning left without checking right
• Missing combined condition for LCA
• Ignoring null root check

5. Given a binary tree where nodes 2 and 4 are in the left subtree of node 3, and nodes 5 and 6 are in the right subtree of node 3, what is the LCA of nodes 2 and 6?

hard

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Understand tree structure

   Nodes 2 and 4 are in left subtree of 3; nodes 5 and 6 are in right subtree of 3.

2. Step 2: Find common ancestor of nodes 2 and 6

   Since 2 is in left subtree and 6 is in right subtree, their lowest common ancestor is the root node 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA of nodes in opposite subtrees is root [OK]

Hint: LCA of nodes in different subtrees is their root [OK]

Common Mistakes:

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