algoadvance

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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).”

Clarifying Questions

1. Can we assume that both nodes p and q are present in the BST?
2. Do the values of the nodes in the BST follow the BST properties strictly (i.e., left child < parent < right child)?
3. Can the given nodes p and q be the same node?
4. Is it guaranteed that the input tree is a valid BST?

Assuming:

• Both p and q are present in the BST.
• The BST properties are strictly followed.
• p and q are distinct nodes.
• The tree is a valid BST.

Strategy

1. Utilize the properties of the BST to guide the search for the LCA.
2. Start from the root node.
3. If both p and q are greater than the current node, move to the right subtree.
4. If both p and q are less than the current node, move to the left subtree.
5. If one of p or q is smaller and the other is larger, then the current node is the LCA.
6. Return the node where the above conditions stop holding true for further traversal.

Code

Here’s the implementation in python:

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Start with the root node
        current = root
        
        # Iterate through the tree
        while current:
            # If both p and q are greater than parent
            if p.val > current.val and q.val > current.val:
                current = current.right
            # If both p and q are lesser than parent
            elif p.val < current.val and q.val < current.val:
                current = current.left
            else:
                # We have found the split point i.e. the LCA node.
                return current

Time Complexity

• The time complexity of this algorithm is O(h), where h is the height of the binary search tree.
• In the best case, the height h could be log(n) for a balanced tree.
• In the worst case, the height h could be n for a degenerate (linked list-like) tree.

Space Complexity

• The space complexity is O(1) as we are using a constant amount of space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?