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.