Finding the Lowest Common Ancestor in a BST using Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF