leetcode-treee

235. Lowest Common Ancestor of a Binary Search Tree.py

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

class Solution:
    """
    For each given current node, we need to determine where to search the common ancestor.
    Then, we leverage properties of bst.
    """
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        T:O(h) since we only search half of tree
        S:O(h) because of recursion stack
        """
        def dfs(r):
            if max(p.val, q.val) < r.val:
                return dfs(r.left)
            elif min(p.val, q.val) > r.val:
                return dfs(r.right)
            else:
                return r
        return dfs(root)