### Python program to find lowest common ancestor in a binary tree

Description:
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.

LCA(4,5) =2
LCA(6,3) =3
LCA(6,7) =3
LCA(5,6) =1

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.

Program:

class Node: # Constructor to create a new binary node def __init__(self, key): self.key = key self.left = None self.right = None # Finds the path from root node to given root of the tree. # Stores the path in a list path[], returns true if path # exists otherwise false def findPath( root, path, k): # Baes Case if root is None: return False # Store this node is path vector. The node will be # removed if not in path from root to k path.append(root.key) # See if the k is same as root's key if root.key == k : return True # Check if k is found in left or right sub-tree if ((root.left != None and findPath(root.left, path, k)) or (root.right!= None and findPath(root.right, path, k))): return True # If not present in subtree rooted with root, remove # root from path and return False path.pop() return False # Returns LCA if node n1 , n2 are present in the given # binary tre otherwise return -1 def findLCA(root, n1, n2): # To store paths to n1 and n2 fromthe root path1 = [] path2 = [] # Find paths from root to n1 and root to n2. # If either n1 or n2 is not present , return -1 if (not findPath(root, path1, n1) or not findPath(root, path2, n2)): return -1 # Compare the paths to get the first different value i = 0 while(i < len(path1) and i < len(path2)): if path1[i] != path2[i]: break i += 1 return path1[i-1] # Driver program to test above function # Let's create the Binary Tree shown in above diagram 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 )))

Output:

LCA(4, 5) = 2
LCA(4, 6) = 3
LCA(3, 4) = 3
LCA(2, 4) = 1
>>>

#### More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 867 20
Tokenize text using NLTK in Python. 1248 12
Python Remove multiple elements from list while Iterating. 773 22
Python How to Check if an item exists in list ? 4320 14
Python How to remove multiple elements from list ? 786 26
Python program to check if two trees are mirror of each other without using recursion. 695 19
Python program to find maximum in Binary tree. 972 19
Python Check if all elements are same using Set 752 15
Python program to find diameter of a binary tree. 1125 20
Python program to print root to leaf paths without using recursion. 870 20
Python program to find root of the tree where children id sum for every node is given. 710 23
Introduction of Python NLTK library 1402 25
Categorizing and Tagging Sentences using NLTK in Python . 1058 19
Python program to find height of a tree without using recursion. 689 16
Python program to find sum of all nodes of the given perfect binary tree. 696 19
Python program to find minimum in binary tree. 859 23
Python Check if element exist in list using list.count() function. 720 13
Python program to convert a given binary tree to doubly linked list. 922 20
Python program to find distance between two nodes of a binary tree. 1561 20
NLTK stop Words 1194 13
Python program to find largest binary search tree in a Binary Tree. 973 20
Python program to find inorder successor in binary search tree with recursion. 1243 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 828 15
Python List check if element are same using all() 713 12
Python program to check if two trees are identical using recursion. 738 30
Python Find the occurrence count of an element in the tuple using count() 1000 23
Python Convert two lists to a dictionary 761 19
Python program to construct a complete binary tree from given array. 1480 14
Python program to find diameter of binary tree in O(n). 907 17
Introduction to the AVL tree. 809 15
Python program to check if two trees are identical without using recursion 692 17
Python Convert a list of tuples to dictionary. 1132 24
Python program to convert a binary tree to a circular doubly link list. 687 21
Python Check if element exist in list based on own logic. 782 23
Python program to merge two binary trees by doing node sum using recursion 1042 27
Python program to check whether a given binary tree is perfect or not. 710 17
Python Check if all elements are same using list.count(). 1125 28
Python program to find an element into binary tree 657 12
Python program to find lowest common ancestor in a binary tree 1254 24