In an earlier tutorial, we have seen
If you have not gone through it, read it here.
In this tutorial, we will find the lowest common ancestor in the binary tree when two nodes are given.
Let’s take the below binary tree example.
The node ‘x’ is the lowest common ancestor of given two nodes if two nodes present on either side (left and right) of ‘x’.
Here is the simple algorithm to find the lowest common ancestors of two nodes (says ‘a’ and ‘b’) in a binary tree.
ancestorsB. This will give you the lowest common ancestor.
Let’s find the common ancestor of nodes 3 and 6.
Use this logic to write a code in any programming language you are comfortable with, like C/C++, Java, Python…
This problem was asked to me in one of the Amazon interview round.
Here we are maintaining two list
ancestorsB to stores all the ancestors of two nodes
#binary tree node structure ancestorsA= ancestorsB= class node: def __init__(self, val, left=None, right=None): self.left=left self.val=val self.right=right #function to print all the ancestors of a given node def findAncestors(root, val, listAncestors): if not root: return False else: if root.val==val: return True else: if findAncestors(root.left,val, listAncestors) or \ findAncestors(root.right,val, listAncestors): listAncestors.append(root.val) return True #create binary tree root=node(4) root.left=node(1) root.right=node(5) root.left.left=node(7) root.left.right=node(3) root.right.right=node(6) nodeA=6 nodeB=3 findAncestors(root, nodeA, ancestorsA) findAncestors(root, nodeB, ancestorsB) for i in range(0, min(len(ancestorsA), len(ancestorsB))): if ancestorsA[i]==ancestorsB[i]: print("The lowest common ancestor in the binary tree \ for nodes %d and %d is %d." \ %(nodeA, nodeB, ancestorsA[i]))
The lowest common ancestor in the binary tree for nodes 6 and 3 is 4.
Note: To find common ancestors, you don’t need to sort the nodes in a Binary tree. This solution works even if the nodes are in an unsorted order.
To calculate the ancestors of any node in the binary tree takes the time of
A total number of ancestors to any node can not exceed
log(n). In the worst case, it takes
O(log(n)) to find the first common ancestor node.
So, the total complexity of this problem is
O(n)+O(n)+O(log(n)) which is equivalent to