JavaScript Coding Test Course, Lowest Common Ancestor

Hello, everyone! In this post, we will explore the ‘Least Common Ancestor (LCA)’ problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process.

Problem Description

This is the problem of finding the least common ancestor of two nodes in a given binary tree. The tree follows these rules:

  • Each node can have at most two children.
  • The given two nodes always exist in the tree.

Input

  • Address of the root node of the tree (root)
  • Address of the first node (node1)
  • Address of the second node (node2)

Output

Print the node value of the least common ancestor of the two nodes.

Example

Input:
          3
         / \
        5   1
       / \ / \
      6  2 0  8
        / \
       7   4
       
       node1 = 5, node2 = 1
       
Output:
3

Solution

There can be several approaches to solve this problem. However, the most common approach is to use DFS (Depth First Search). This method allows us to find the least common ancestor by visiting each node. Let’s examine this process step by step.

Step 1: Define the Tree Structure

First, we need to create a class defining the tree. In JavaScript, a tree node can generally be defined as follows:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null; // left child
        this.right = null; // right child
    }
}

Step 2: Create the Tree

Let’s write sample code to create the tree. The following code creates a tree like the one in the example above:

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

Step 3: Implement the DFS Algorithm

Now it’s time to implement the DFS algorithm. The process for finding the least common ancestor follows these steps:

  1. If the current node is null, return null.
  2. If the current node is equal to node1 or node2, return the current node.
  3. Recursively call the left and right children to obtain the results.
  4. If both left and right child node results are not null, the current node is the least common ancestor.
  5. If only one of the left or right children is not null, return the non-null child.
function lowestCommonAncestor(root, node1, node2) {
    if (root === null) return null;
    if (root.value === node1.value || root.value === node2.value) return root;

    const left = lowestCommonAncestor(root.left, node1, node2);
    const right = lowestCommonAncestor(root.right, node1, node2);

    if (left && right) return root;
    return left ? left : right;
}

Step 4: Output the Result

Now that the least common ancestor algorithm is complete, let’s test it:

const lca = lowestCommonAncestor(root, root.left, root.right); // node1: 5, node2: 1
console.log(lca.value); // 3

Summary and Conclusion

In this post, we covered the Least Common Ancestor (LCA) problem. We defined the tree structure, implemented an algorithm using DFS, and verified the results through examples. The key point is that this algorithm visits each node through recursive calls, structurally setting conditions to find the least common ancestor.

Such problems have various forms, so it is important to practice solving different types of problems. We will continue to introduce various algorithms that will help you prepare for JavaScript coding tests, so please stay tuned!

References

I hope this helps you prepare for your coding tests. Thank you!