235. Lowest Common Ancestor of a Binary Search Tree#

Difficulty: Medium

Link to Problem: To see the Lowest Common Ancestor of a Binary Search Tree problem on LeetCode, click here!

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Constraints:

  • The number of nodes in the tree is in the range \([2, 10^5]\).

  • \(-10^9\) <= Node.val <= \(10^9\)

  • All Node.val are unique.

  • p != q

  • p and q will exist in the BST.

Solution:#

Here’s a Python function to solve this problem:

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):
    # Ensure p is less than q
    if p.val > q.val:
        p, q = q, p

    while root:
        # If the current node value is greater than both p and q, move left
        if root.val > q.val:
            root = root.left
        # If the current node value is less than both p and q, move right
        elif root.val < p.val:
            root = root.right
        # If the current node value is between p and q (inclusive), or it matches either p or q, it's the LCA
        else:
            return root

Explanation:#

  1. class TreeNode: defines a simple class for representing nodes in a binary tree. Each TreeNode has three attributes:

    • val: The value of the node.

    • left: A reference to the left child node.

    • right: A reference to the right child node.

  2. def lowestCommonAncestor(root, p, q): is a function that takes three arguments:

    • root: The root node of the BST.

    • p: A TreeNode representing one of the nodes for which we want to find the LCA.

    • q: A TreeNode representing the other node for which we want to find the LCA.

  3. if p.val > q.val: checks if the value of p is greater than the value of q. In a BST, it’s essential to ensure that p represents the smaller value, and q represents the larger value. If p is greater than q, the code swaps their values.

  4. The main logic is inside the while loop, which runs until root becomes None. It performs the following steps to find the LCA:

    • If the current root node’s value is greater than the value of q, it means both p and q are on the left subtree of the current node. So, we move to the left child of the current node by setting root = root.left.

    • If the current root node’s value is less than the value of p, it means both p and q are on the right subtree of the current node. So, we move to the right child of the current node by setting root = root.right.

    • If neither of the above conditions is met, it means the current root node’s value is between p and q, or it matches either p or q. In this case, the current node is the lowest common ancestor (LCA), so we return root.

The algorithm is efficient because it takes advantage of the properties of a BST. It eliminates subtrees that cannot contain the LCA by comparing the values of p, q, and the current root node. Eventually, it reaches the LCA node, and that node is returned as the result.

Test cases#

# Example 1: 

# Construct the tree
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  # Node 2
q = root.right  # Node 8

result = lowestCommonAncestor(root, p, q)
print(result.val)

6

# Example 2:

# Using the same tree as before
p = root.left  # Node 2
q = root.left.right  # Node 4

result = lowestCommonAncestor(root, p, q)
print(result.val) 

2

# Example 3:
# Creating a new tree for this example
root2 = TreeNode(2)
root2.left = TreeNode(1)

p = root2  # Node 2
q = root2.left  # Node 1

result = lowestCommonAncestor(root2, p, q)
print(result.val)

2

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided algorithm for finding the lowest common ancestor (LCA) in a Binary Search Tree (BST).

Time Complexity: The time complexity of this algorithm is O(h), where “h” is the height of the BST. In the worst case, where the tree is completely unbalanced (essentially a linked list), the height of the tree is O(n), where “n” is the number of nodes in the tree. However, in a well-balanced BST, the height is logarithmic, which is O(log n).

The reason for this time complexity is that the algorithm efficiently narrows down the search space by traversing either left or right subtrees based on the values of the target nodes p and q. It eliminates entire subtrees that cannot contain the LCA, leading to a relatively quick search.

Space Complexity: The space complexity of the algorithm is O(1). This is because it uses a constant amount of extra space, regardless of the size of the input BST. The only variables used are root, p, and q, and there are no data structures like stacks or queues used for additional space. The algorithm performs a simple traversal without recursion, so it does not consume extra memory as the tree depth increases.

In summary, the provided algorithm for finding the LCA in a BST is both time and space-efficient. Its time complexity is O(h), where “h” is the height of the tree, and its space complexity is O(1), making it suitable for practical use even in large BSTs.

Challenging Exercises:#

  1. Multiple LCAs: Extend the algorithm to find all the lowest common ancestors of two given nodes p and q in a BST. In some cases, there can be multiple LCAs.

  2. LCA with k Nodes: Given a BST and k nodes, find the lowest common ancestor of these k nodes. This is an extension of the problem where you must find the LCA of more than two nodes.