236 Lowest Common Ancestor of a Binary Tree

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.

The Idea: We know that the lowest common ancestor will intersect in paths as we iterate from both nodes towards the root of the tree. I am reminded of the problem that identifies the intersection two linked lists. Since one path can be longer than the other, with the linked lists, what we can do is find out the lengths of both linked lists and iterate the longer linked list the difference of the lengths. This way when we iterate both linked lists together, they will be the same length, and the intersection of paths will be when the iterators are the same value.

The same idea is found here, but instead, we build two paths. One to node a, and a second path to node b. Then, we begin iterating backwards from the smaller length path until we find a match (same as the linked lists). Since we know both paths cannot be empty, and the highest common ancestor is the root, the algorithm should be able to terminate in that for loop.

Complexity: O(3n) time and O(n) space

# 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
        """

        def path_to_x(root, path, x, go):
            if root is not None and go[0]:
                path.append(root.val)
                if root.val == x:
                    go[0] = False
                path_to_x(root.left, path, x, go)
                path_to_x(root.right, path, x, go)
                if go[0]:
                    path.pop()

        path_p = []
        go = [True]
        path_to_x(root, path_p, p, go)

        path_q = []
        go[0] = True
        path_to_x(root, path_q, q, go)

        strt = min(len(path_p), len(path_q)) - 1
        for i in range(strt, -1, -1):
            if path_p[i] == path_q[i]:
                return path_p[i]