[LeetCode] Lowest Common Ancestor of a Binary Search Tree

 

 

Problem

 

 

---

 

Solution

 

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)

 

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

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        # If p and q are on the same subtree of the current node,
        # update ancester to its child node
        # If they are on different subtree, current node is the final result
        # If current node is updated to child node, and that node is equal to p or q, p or q is the result
        if not root:
            return root
        
        ancester = root
        curr = root
        
        while True:
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left
                ancester = curr
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
                ancester = curr
            else:
                return curr