Mastering the Lowest Common Ancestor of a Binary Search Tree: Implementations in Java and Python

The Lowest Common Ancestor (LCA) of a Binary Search Tree (BST) is a fascinating problem that often arises in the domain of data structures and algorithms. In this blog, we will explore the intricacies of finding the LCA of a BST and provide a step-by-step solution. By understanding the underlying concepts and examining implementation examples, you will gain the knowledge and skills needed to tackle this problem with confidence.

 

Understanding the Problem:

Given a Binary Search Tree and two nodes, our goal is to find their lowest common ancestor. The LCA is the deepest node in the BST that is an ancestor of both given nodes. It represents the shared parent node of the two nodes in the BST hierarchy.

 

Approach:

To find the LCA of two nodes in a BST, we can leverage the characteristics of a BST and utilize a recursive approach. The key steps of the algorithm are as follows:

1. Start from the root of the BST.
2. Compare the values of the current node with the values of the two given nodes.
3. If both values are smaller than the current node value, move to the left subtree recursively.
4. If both values are greater than the current node value, move to the right subtree recursively.
5. If one value is smaller and the other is greater than the current node value, then the current node is the LCA.
6. Repeat steps 2 to 5 until the LCA is found.

 

Java Implementation:

Let's start with the Java implementation of finding the Lowest Common Ancestor of a BST:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LowestCommonAncestorBST {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null)
            return null;

        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        else
            return root;
    }

    public static void main(String[] args) {
        LowestCommonAncestorBST lca = new LowestCommonAncestorBST();

        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);

        TreeNode p = root.left.right.left;
        TreeNode q = root.left.right.right;

        TreeNode lcaNode = lca.lowestCommonAncestor(root, p, q);
        System.out.println("Lowest Common Ancestor: " + lcaNode.val);
    }
}

 

Python Implementation:

Now, let's explore the Python implementation of finding the Lowest Common Ancestor of a BST:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class LowestCommonAncestorBST:
    def lowestCommonAncestor(self, root, p, q):
        if not root or not p or not q:
            return None

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

lca = LowestCommonAncestorBST()

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)

p = root.left.right.left
q = root.left.right.right

lcaNode = lca.lowestCommonAncestor(root, p, q)
print("Lowest Common Ancestor:", lcaNode.val)

 

Conclusion: 

In this blog post, we explored the concept of finding the Lowest Common Ancestor (LCA) of a Binary Search Tree (BST). We provided detailed implementations in both Java and Python, demonstrating how to efficiently solve this problem using recursive techniques. By understanding the logic behind the LCA algorithm and examining the code examples, you now have the tools to confidently find the LCA of any two nodes in a BST. Enhance your programming skills by practicing with different BST scenarios and optimizing the code for your specific requirements.