Lowest Common Ancestor of a Binary Search Tree

Intuition

Using DFS, and in the dfs function, return 2 values p_visited and q_visited. When the first time p_visited equals to q_visited, set the result and return the result.

Solution


# 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':
        self.result = None
        self._helper(root, p, q)
        return self.result

    def _helper(self, node, p, q):
        if node is None:
            return False, False
        lp, lq = self._helper(node.left, p, q)
        rp, rq = self._helper(node.right, p, q)
        cp, cq = (p == node), (q == node)
        vp, vq = (lp or rp or cp), (lq or rq or cq)
        if vp and vq and self.result is None:
            self.result = node
        return vp, vq