The Binary Tree here is may not necessarily be a Binary Search Tree.
The structure could be taken as -
struct node {
int data;
struct node *left;
struct node *right;
};
The maximum solution I could work out with a friend was something of this sort -
Consider this binary tree :
Binary Tree http://lcm.csa.iisc.ernet.in/dsa/img151.gif
The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7
And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1
So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.
The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)
But this is a very crude approach, and I'm not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?
Here is the C++ way of doing it. Have tried to keep the algorithm as much easy as possible to understand:
How to use it:
Some of the solutions here assumes that there is reference to the root node, some assumes that tree is a BST. Sharing my solution using hashmap, without reference to
root
node and tree can be BST or non-BST:Just walk down from the whole tree's
root
as long as both given nodes ,sayp
andq
, for which Ancestor has to be found, are in the same sub-tree (meaning their values are both smaller or both larger than root's).This walks straight from the root to the Least Common Ancestor , not looking at the rest of the tree, so it's pretty much as fast as it gets. A few ways to do it.
in case of overflow, I'd do (root.val - (long)p.val) * (root.val - (long)q.val)
Although this has been answered already, this is my approach to this problem using C programming language. Although the code shows a binary search tree (as far as insert() is concerned), but the algorithm works for a binary tree as well. The idea is to go over all nodes that lie from node A to node B in inorder traversal, lookup the indices for these in the post order traversal. The node with maximum index in post order traversal is the lowest common ancestor.
This is a working C code to implement a function to find the lowest common ancestor in a binary tree. I am providing all the utility functions etc. as well, but jump to CommonAncestor() for quick understanding.
The easiest way to find the Lowest Common Ancestor is using the following algorithm: