Finding the Lowest Common Ancestor in a BST using Java

In computer science, especially when working with tree data structures, the concept of the "Lowest Common Ancestor" (LCA) becomes quite relevant. In a Binary Search Tree (BST), for two given nodes, the LCA is the node in the BST where both nodes descend from, but that is located as deeply as possible in the tree. In this article, we're going to implement and understand the algorithm to find the LCA of two nodes in a BST. 

Understanding the Problem

Given a BST and two nodes p and q, we have to find the node whose value lies between p and q (i.e., min(p, q) <= node <= max(p, q)). This node will be the LCA of p and q. 

Program Implementation

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    Node findLCA(int n1, int n2) {
        return findLCA(root, n1, n2);
    }

    Node findLCA(Node node, int n1, int n2) {
        // Base case
        if (node == null) {
            return null;
        }

        // If node's value is greater than both n1 and n2, then LCA lies in left
        if (node.data > n1 && node.data > n2) {
            return findLCA(node.left, n1, n2);
        }

        // If node's value is smaller than both n1 and n2, then LCA lies in right
        if (node.data < n1 && node.data < n2) {
            return findLCA(node.right, n1, n2);
        }

        return node;
    }

    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();
        Node root = new Node(20);
        tree.root = root;
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);

        int n1 = 8, n2 = 12;
        Node t = tree.findLCA(n1, n2);
        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
    }
}

Output:

LCA of 8 and 12 is 8

Step-by-step Explanation: 

Node Class: Represents each node in our BST. Contains integer data and references to left and right children. 

findLCA() Methods: We have two findLCA methods. One is a utility function, while the other is the recursive function that does the main work. It checks the current node's value and determines if the LCA lies to the left, or right, or if the current node is the LCA. 

Main Method: We create a sample BST. Next, we call the findLCA method passing two node values, and then print the result.