236.Lowest Common Ancestor of a Binary Tree

Tags: [tree], [binary_tree], [ancestor], [BFS], [parent], [path], [tree_path], [extend_function_meaning]

Com: {fb}

Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description

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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes5and1is3. Another example is LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.

Solution: BFS, Parents, Path

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

from collections import deque

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None

        # BFS to collect the parents for each node
        parents = {root: None}
        queue = deque()
        queue.append(root)

        while queue:
            curr = queue.popleft()
            if curr.left:
                queue.append(curr.left)
                parents[curr.left] = curr

            if curr.right:
                queue.append(curr.right)
                parents[curr.right] = curr

        # get the path from p to root
        p_path = [p]
        tmp_p = p
        while tmp_p:
            parent = parents[tmp_p]
            p_path.append(parent)
            tmp_p = parent

        # get the path from q to root
        q_path = [q]
        tmp_q = q
        while tmp_q:
            parent = parents[tmp_q]
            q_path.append(parent)
            tmp_q = parent

        # find the lowest common ancestor
        ancestor = None
        p_index = len(p_path) - 1
        q_index = len(q_path) - 1
        while p_index >= 0 and q_index >= 0:
            if p_path[p_index] != q_path[q_index]:
                break

            ancestor = p_path[p_index]
            p_index -= 1
            q_index -= 1

        return ancestor

Revelation:

• Using BFS can build the paths, because BFS scan the tree level by level, we can know the relationship between the node and its parent.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(n), n is the number of nodes of the given tree.

Another Solution: Recursion, Assuming the tree must contains both p and q

# 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 root in set([None, p, q]):
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        return left if left else right

Revelation:

• Extend the meaning of the function 'lowestCommonAncestor': if the function find p, then return p, if the function find q, then return q, if the function cannot find p and q, then return None. So in short, the function first find p return p, first find q return q, if cannot find p and q, return None, which means this function assume the tree must contains p and q.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree, because each node only get visited once.
• Space complexity = O(h), h is the height of the tree.