LCA in BST 🎯

Welcome to a deep dive into the world of Data Structures and Algorithms! Today, we're going to explore one of the essential concepts in Binary Search Trees (BST) - LCA (Lowest Common Ancestor).

Let's start with a real-world example. Imagine you're managing a large organization, and employees can be represented as nodes in a BST. You want to find the lowest common ancestor of two employees in the organization hierarchy. Sounds exciting, right? 📝

Understanding BST 📝

Before we delve into LCA, let's quickly review what a Binary Search Tree is. A BST is a binary tree data structure where each node has at most two children: the left child and the right child. The BST follows the rule that the key value of the left child node is always less than the parent node, and the key value of the right child node is always greater than the parent node.

What is LCA in BST? 💡

In a BST, LCA (Lowest Common Ancestor) is the unique node that is an ancestor of both the given nodes in the tree. In simpler terms, it is the lowest node that is a common ancestor to two other nodes.

Finding LCA in BST 🎯

Now, let's find the LCA for two nodes in a BST using the simplest approach - Path-based Method.

python

def findLCA(root, n1, n2):
    if root is None or root.data == n1 or root.data == n2:
        return root

    if root.data > n1 and root.data > n2:
        return findLCA(root.left, n1, n2)

    if root.data < n1 and root.data < n2:
        return findLCA(root.right, n1, n2)

    # If the node is not in the left or right subtree, then LCA is in the other subtree.
    # We have to find LCA recursively in the other subtree.
    if root.data < n1:
        right_subtree_lca = findLCA(root.right, n1, n2)
    else:
        left_subtree_lca = findLCA(root.left, n1, n2)

    return root if root is left_subtree_lca or root is right_subtree_lca else left_subtree_lca if left_subtree_lca else right_subtree_lca

💡 Pro Tip: This method works well when the tree is balanced. For an unbalanced tree, you may want to consider other approaches like the Path-Length-based Method or the Inorder-Traversal-based Method.

Practical Application 📝

Finding the LCA in a BST is a common problem in various real-world applications, such as:

Finding the earliest common ancestor of two employees in an organization hierarchy.
Determining the page that contains a common ancestor for two given web pages in a website.
Finding the common ancestor of two genes in a genetic tree.

Quiz 📝

Stay tuned for more exciting lessons on Data Structures and Algorithms! Let's continue exploring the fascinating world of coding together. 🚀💻