Question

How can you find the Lowest Common Ancestor in a Binary Search Tree?

Answer 1

To find the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST), you can use a simple algorithm that exploits the properties of BSTs. Here's how you can find the LCA efficiently:

1. Start from the root of the BST.
2. Traverse down the tree, comparing the values of the current node with the values of the two target nodes.
3. If the current node's value is greater than both target nodes' values, move to the left subtree.
4. If the current node's value is less than both target nodes' values, move to the right subtree.
5. If the current node's value falls between the values of the two target nodes, or if one of the target nodes' value matches the current node's value, then the current node is the LCA.
6. Continue traversing until you find the LCA.

Here's the algorithm in Python:

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

def find_LCA(root, node1, node2):
    if root is None:
        return None
    
    # If both nodes are smaller than root, LCA lies in left
    if root.value > node1 and root.value > node2:
        return find_LCA(root.left, node1, node2)
    
    # If both nodes are greater than root, LCA lies in right
    if root.value < node1 and root.value < node2:
        return find_LCA(root.right, node1, node2)
    
    # Otherwise, the current node is the LCA
    return root.value

# Example usage:
# Assuming 'root' is the root node of the binary search tree
# and node1, node2 are the values of the nodes whose LCA is to be found
# lca = find_LCA(root, node1, node2)
 

This algorithm exploits the property of the BST where nodes to the left have values smaller than the current node, and nodes to the right have values greater than the current node. By recursively traversing down the tree and comparing node values, we can efficiently find the LCA of the given nodes. The time complexity of this algorithm is O(h), where h is the height of the tree, and in a balanced BST, it is approximately O(log n), where n is the number of nodes in the tree.