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).”
/ \ / \
6 _2 0 8
For example, the lowest common ancestor (LCA) of nodes
3. Another example is LCA of nodes
5, 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
def lowestCommonAncestor(self, root, p, q):
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
def path_to_x(root, path, x, go):
if root is not None and go:
if root.val == x:
go = False
path_to_x(root.left, path, x, go)
path_to_x(root.right, path, x, go)
path_p = 
go = [True]
path_to_x(root, path_p, p, go)
path_q = 
go = 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]: