Leetcode 236 Lowest Common Ancestor of a Binary Tree

Problem description

Leetcode 236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
• Output: 3
• Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
• Output: 5
• Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

• Input: root = [1,2], p = 1, q = 2
• Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Process

Let lca_node be the lowest common ancestor of nodes p and q. Then lca_node must satisfy one of the following:

1. p and q are in the left and right subtrees of lca_node, respectively.
2. p == lca_node, and q is in either the left or right subtree of lca_node.
3. q == lca_node, and p is in either the left or right subtree of lca_node.

To find lca_node recursively, the following conditions should be met:

• If both p and q are not null, return their common ancestor.
• If only one of p or q exists, return the one that exists.
• If neither p nor q exists, return None.

Detailed Algorithm

1. If the current node node equals p or q, then node is the lowest common ancestor of p and q.
   → Return node.

2. If the current node node is not null, recursively search both left and right subtrees:
   • If both left and right subtree results are not null, it means p and q are on different sides, and the current node is their LCA.
     → Return node.
   • If the left subtree is null, return the result from the right subtree.
   • If the right subtree is null, return the result from the left subtree.
   • If both are null, return None.
3. If the current node node is None, then neither p nor q are in this subtree.
   → Return None.

Code

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == p or root == q:
            return root

        if root:
            node_left = self.lowestCommonAncestor(root.left, p, q)
            node_right = self.lowestCommonAncestor(root.right, p, q)
            if node_left and node_right:
                return root
            elif not node_left:
                return node_right
            else:
                return node_left
        return None

Time complexity and space complexity

• Time complexity：\(O(n)\)，where \(n\) is number of node of tree。
• Space complexity：\(O(n)\)。

Reference