Skip to main content

Lowest Common Ancestor of a Binary Tree

Question​

None

Example 1
Input: 

Tree: 
       3
      / \
     5   1
    / \ / \
   6  2  0  8
       \
        7

p = 5, q = 1

Output: 3

Solution​

all//Lowest Common Ancestor of a Binary 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:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None:
            return None
        if root == p or root == q:
            return root
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)

        if left_lca and right_lca:
            return root
        return left_lca if left_lca is not None else right_lca