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.