Question

Can you provide an example code for finding the Lowest Common Ancestor in a Binary Search Tree?

Answer 1

Here is the code.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

# Example usage:
# Construct the binary search tree
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

p = root.left
q = root.right
lca_node = lowestCommonAncestor(root, p, q)
print("Lowest Common Ancestor:", lca_node.val)  # Output: 6
 

This example code demonstrates how to find the Lowest Common Ancestor of two nodes in a Binary Search Tree and prints the value of the LCA node.