Explanation: LCA is the first root satisfying min(p,q) <= root <= max(p,q) in while loop


  • 1
    A

    Let me begin by stating the key fact:
    LCA is the first root satisfying min(p,q) <= root <= max(p,q) in while loop

    The key fact is simple, so is the code:

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

    Here is the explanation:

    First, let's say we encounter root satisfying min(p,q) <= root <= max(p,q). This root is clearly common ancestor of both p and q due to BST property. Why this is the LOWEST common ancestor? Why root cannot go any deeper like root = root.left or root = root.right?

    OK, if root goes to left further, root.left could still be common ancestor ONLY IF p and q are both on the left subtree of root due to ancestor requirement. It means p,q < root, which leads to a contradiction to min(p,q) <= root <= max(p,q).

    Similarly, root cannot go to right further.

    Life is short. Keep code neat.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.