JavaScript Coding Test Course, Finding Least Common Ancestor 2

Problem Description

This problem involves finding the Lowest Common Ancestor (LCA) of two nodes.
Given a binary tree, the goal is to find the common ancestor of two specified nodes.

Input Format

  • The root node of the binary tree is given.
  • Two node values are provided.

Output Format

  • The value of the Lowest Common Ancestor of the given two nodes, or -1 if it does not exist.

Example Problems

    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 4 and 5 is 2.
  
    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 4 and 3 is 1.

    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 6 and 7 is -1.

Problem Solution

To solve this problem, we approach it with the following steps:

  1. Define the binary tree structure:
    First, we define a node class to represent the structure of the tree. This class has a value for the node,
    and properties that reference left and right child nodes.
  2. Recursive Approach:
    To find the lowest common ancestor, we recursively traverse the tree.
    If the current node corresponds to ${p} or ${q}, we return the current node.
  3. Check Left and Right Subtrees:
    We find the LCA in both the left and right subtrees, and if both results exist,
    the current node is the LCA.
  4. Return Result:
    If both nodes are found, return the current node; otherwise, return null.

JavaScript Code Implementation


// Define a binary tree node class
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Function to find the lowest common ancestor
function findLCA(root, p, q) {
    // Base case: when the current node is null
    if (root === null) {
        return null;
    }
    
    // If the current node is p or q, return the current node
    if (root.value === p || root.value === q) {
        return root;
    }
    
    // Find LCA in left and right subtrees
    const leftLCA = findLCA(root.left, p, q);
    const rightLCA = findLCA(root.right, p, q);
    
    // If results exist in both left and right, the current node is LCA
    if (leftLCA && rightLCA) {
        return root;
    }
    
    // Return the result found in one of the subtrees
    return leftLCA !== null ? leftLCA : rightLCA;
}

// Example usage
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const node1 = 4;
const node2 = 5;
const lca = findLCA(root, node1, node2);
console.log(lca ? lca.value : -1); // Output: 2

Conclusion

Finding the lowest common ancestor is an important search problem in binary trees.
It can be solved efficiently through a recursive approach for various tree structures and nodes.
This method is useful in many situations and will greatly aid in understanding recursive thinking and tree traversal.

Additional Tasks

Try to solve the following additional tasks!

  • Add logic to handle the case where the given nodes do not exist.
  • Research and implement an optimized method to find the LCA in a binary search tree.
  • Also, implement a function to visualize various tree structures.

References