{"id":27236,"date":"2018-01-05T21:50:37","date_gmt":"2018-01-05T16:20:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27236"},"modified":"2018-10-31T11:05:42","modified_gmt":"2018-10-31T05:35:42","slug":"python-program-lowest-common-ancestor-binary-search-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-lowest-common-ancestor-binary-search-tree\/","title":{"rendered":"Lowest Common Ancestor in a Binary Search Tree"},"content":{"rendered":"

Python Program Lowest Common Ancestor in Binary Search Tree:<\/strong><\/span><\/p>\n

Given values of two nodes in a Binary Search Tree<\/a>, write a Python<\/a> program to find the L<\/strong>owest C<\/strong>ommon A<\/strong>ncestor (LCA<\/strong>). You may assume that both the values exist in the tree.<\/span><\/p>\n

The function prototype should be as follows:<\/p>\n

 struct node *lca(node* root, int n1, int n2)\r\n n1 and n2 are two given values in the tree with given root.\r\n\"<\/pre>\n
For example, consider the BST<\/a> in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.<\/p>\n
Following is definition of LCA from Wikipedia:<\/strong><\/span><\/h3>\n
Let T be a rooted tree. The lowest common ancestor<\/a> 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).<\/p>\n
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. (Source Wiki)<\/p>\n
<\/div>\n[ad type=”banner”]\n
If we are given a BST where every node has parent pointer<\/strong>, then LCA can be easily determined by traversing up using parent pointer and printing the first intersecting node.<\/p>\n
We can solve this problem using BST properties. We can recursively traverse<\/strong> the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node\u2019s value is greater than both n1 and n2 then our LCA lies in left side of the node, if it\u2019s is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)<\/p>\n
Implementation of Python Program:<\/span><\/h3>\n
 
 Python Programming<\/span> <\/div> 
# A recursive python program to find LCA of two nodes# n1 and n2 # A Binary tree nodeclass Node:     # Constructor to create a new node    def __init__(self, data):        self.data = data        self.left = None        self.right = None # Function to find LCA of n1 and n2. The function assumes# that both n1 and n2 are present in BSTdef lca(root, n1, n2):         # Base Case    if root is None:        return None     # If both n1 and n2 are smaller than root, then LCA    # lies in left    if(root.data > n1 and root.data > n2):        return lca(root.left, n1, n2)     # If both n1 and n2 are greater than root, then LCA    # lies in right     if(root.data < n1 and root.data < n2):        return lca(root.right, n1, n2)     return root # Driver program to test above function # Let us construct the BST shown in the figureroot = Node(20)root.left = Node(8)root.right = Node(22)root.left.left = Node(4)root.left.right = Node(12)root.left.right.left = Node(10)root.left.right.right = Node(14) n1 = 10 ; n2 = 14t = lca(root, n1, n2)print "LCA of %d and %d is %d" %(n1, n2, t.data) n1 = 14 ; n2 = 8t = lca(root, n1, n2)print "LCA of %d and %d is %d" %(n1, n2 , t.data) n1 = 10 ; n2 = 22t = lca(root, n1, n2)print "LCA of %d and %d is %d" %(n1, n2, t.data) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
LCA of 10 and 14 is 12\r\nLCA of 14 and 8 is 8\r\nLCA of 10 and 22 is 20<\/pre>\n
Time complexity<\/strong><\/span> of above solution is O(h)<\/strong> where h is height of tree.<\/p>\n
Also, the above solution requires O(h) extra space in function call stack for recursive function<\/a> calls. We can avoid extra space using iterative solution<\/strong>.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Program – Lowest Common Ancestor in a Binary Search Tree – Data Structure – write a c program to find the Lowest Common Ancestor (LCA).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,1,4148],"tags":[81200,81199,81203,81204,81202,81201,81238,81207,79469,81232,81226,81237,81224,70280,81235,81213,81234,81222],"class_list":["post-27236","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-coding","category-python","tag-lowest-common-ancestor-binary-search-tree","tag-lowest-common-ancestor-binary-tree","tag-lowest-common-ancestor-binary-tree-parent-pointer","tag-lowest-common-ancestor-n-ary-tree","tag-lowest-common-ancestor-of-a-binary-tree-java","tag-lowest-common-ancestor-of-a-binary-tree-leetcode","tag-lowest-common-ancestor-of-a-binary-tree-python","tag-node-interview-questions","tag-on","tag-questions-on-binary-search-tree","tag-questions-on-binary-tree","tag-range-minimum-query","tag-range-tree","tag-search-tree","tag-sparse-table","tag-table-trees","tag-tree-interview-questions","tag-tree-interview-questions-and-answers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27236","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27236"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27236\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27236"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27236"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}