Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor.
Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).
The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor.
Method 1 (By Storing root to n1 and root to n2 paths):
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def findPath( root, path, k):
if root is None:
if root.key == k :
if ((root.left != None and findPath(root.left, path, k)) or
(root.right!= None and findPath(root.right, path, k))):
def findLCA(root, n1, n2):
path1 = 
path2 = 
if (not findPath(root, path1, n1) or not findPath(root, path2, n2)):
i = 0
while(i < len(path1) and i < len(path2)):
if path1[i] != path2[i]:
i += 1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print ("LCA(4, 5) = %d" %(findLCA(root, 4, 5,)) )
print ("LCA(4, 6) = %d" %(findLCA(root, 6, 3)) )
print ("LCA(3, 4) = %d" %(findLCA(root,6,7)) )
print ("LCA(2, 4) = %d" %(findLCA(root,5,6 )))
LCA(4, 5) = 2
LCA(4, 6) = 3
LCA(3, 4) = 3
LCA(2, 4) = 1