Finding the common ancestor in a binary tree
This question was asked to me in an interview: I have a binary tree and I have to find the common ancestor (parent) given two random nodes of that tree. I am also given a pointer to the root node.
My answer is:
Traverse the tree separately for both the nodes till you reach the node that is expected. Parallel while traversing store the element and the next address in a linked list. Then we have two linked lists with us. So try comparing the two linked lists and the last common node in both the linked lists is the parent.
I am thinking that this solution is correct, correct me if I am wrong. If this solution is corr开发者_JAVA技巧ect, may I know is this the only better solution for this task or is there any other better solution than this!
Maybe silly approach:
Generate the path from each node to the root, storing it as a string of "L" and "R".
Reverse these strings. Take the longest common prefix - you now have the path to the common ancestor.
Set a pointer at both of the random nodes. Find the depth of each node by traversing to the top and counting the distance from the root node. Then set the pointer at both nodes again. For the deeper node, traverse up until both pointers are at the same depth. Then traverse up for both nodes until the pointers point to the same node. That is the ancestor node.
By "traverse up" I just mean move the pointer to the parent of the current node.
Edit to clarify: The key idea is that when both nodes are at the same depth, you can find the common parent very quickly just by simple traversal. So you climb the lower one until both are at the same depth, and then you traverse up. Sorry I don't really know C or I'd write code, but that algorithm should answer your question.
Edit again: And my method runs in O(log(n)) time and O(1) memory.
Another edit: O(log(n)) in a balanced tree. Worst-case performance is O(n) for an unbalanced tree. Thanks @DaveCahill
I think you could just do a search simultaneously for both nodes; the point at which the search diverges is the common ancestor.
commonAncestor tree a b:
value := <value of node 'tree'>
if (a < value) && (b < value)
then commonAncestor (left tree) a b
else if (a > value) && (b > value)
then commonAncestor (right tree) a b
else tree
Interestingly this approach would scale to more than two nodes (check for all of them to be on the left side of tree, etc.)
Make a level order traversal, and for each node we encounter we check its children. If they are the provided random nodes, then the ancestor node is found.
EDIT1:
Here is an outline
struct _node {
my_type data;
struct _node *left;
struct _node *right;
}
q = queue_create ();
queue_insert (q, head);
temp = head;
while (!empty (q))
{
temp = queue_remove (q);
if (
(temp->left == my_random_node_1) && (head->right == my_random_node_2) ||
(temp->left == my_random_node_2) && (head->right == my_random_node_1)
)
{
/* temp is the common parent of the two target notes */
/* Do stuffs you need to do */
}
/* Enqueue the childs, so that in successive iterations we can
* check them, by taking out from the queue
*/
push (q, temp->left);
push (q, temp->right);
}
UPDATE
The previous algorithm will only find common parents (direct ancestor), therefore if two randomly selected nodes if are not a child of common parent no answer would be found.
The below algorithm will find common ancestors and not only parents.
I think the following algorithm will work:
Make a postorder traversal of the binary tree, and find for the random node 1 r1, if we find it then mark it in a state variable to be in state one, and keep finding for the second node, if found then update the state variable to state two, and stop searching more and return. The state variable should be passed by every node to its parents (recursively). The first node which encounters the state variable in state two is the common ancestor.
The implementation of the algorithm is as follows:
int postorder (node *p, int r1, int r2)
{
int x = 0; /* The state variable */
if (p->data == TERMINAL_VAL)
return x;
/* 0x01 | 0x02 = 0x03 threfore
* state one is when x = 0x01 or x = 0x02
* state two is when x = 0x03
*/
if (p->data == r1)
x |= 0x01;
else if (p->data == r2)
x |= 0x02;
/* if we have x in state two, no need to search more
*/
if (x != 0x03)
x |= postorder (p->left, r1, r2);
if (x != 0x03)
x |= postorder (p->right, r1, r2);
/* In this node we are in state two, print node if this node
* is not any of the two nodes r1 and r2. This makes sure that
* is one random node is an ancestor of another random node
* then it will not be printed instead its parent will be printed
*/
if ((x == 0x03) && (p->data != r1) && (p->data != r2))
{
printf ("[%c] ", p->data);
/* set state variable to 0 if we do not want to print
* the ancestors of the first ancestor
*/
x = 0;
}
/* return state variable to parent
*/
return x;
}
I think this will work correctly, though i am still to prove the algorithm's correctness. There is one drawback, which is, if one node is a child of another node, then it will print only the node which is the parent of the other one, instead of printing the parent of them. If one of the random node is an ancestor of another random node then instead of printing the ancestor random node, it will print the parent of it. In the case in which one of the random node is the root node, it will print nothing, as it is always the ancestor of the other random node, and therefore their common ancestor does not exist. In this special case the function will return 0x03 in main and it can be detected.
As this algorithm does a postorder traversal therefore it requires O(n) execution time and thus O(n) memory. Also as the search stops as soon both the nodes are found, the shallower the nodes the quicker the search ends.
UPDATE
Here are some mode discussions: How to find the lowest common ancestor of two nodes in any binary tree?
This problem has been very well-studied and there are known algorithms that can solve it in linear time. This paper describes many different approaches you can use to solve it. Admittedtly it is a research paper and so the algorithms are a bit tricky, but some of the approaches it describes are actually quite feasible.
@Above, this will not work, because you are assuming that both nodes are immediate child of some particular node...
8
10 12
7
and I gave the nodes as 7 and 12, answer must be 8. Lets do like this
find(root, d1, d2, n1=null, n2=null)
{
if(n1 && n2) return;
if(!root) return;
else if(root -> d == d1 ) n1 = root;
else if(root -> d == d2 ) n2 = root;
find(root->left, d1, d2, n1, n2);
find(root->right, d1, d2, n1, n2);
}
LCA(root, d1, d2)
{
node *n1=null, *n2=null;
find(root, d1, d2, n1, n2);
if(n1 == null || n2 == null )error 'nodes not present' exit(0);
findIntersect(n1, n2);
}
findInterSect(node *n1, node *n2)
{
l1 = length(n1);
l2 = length(n2);
node *g = n2, *l = n1;
diff = abs(l1 - l2);
if(l1>l2) g = n1 l =n2
while(diff) g = g->parent; diff--;
// now both nodes are at same level
while(g != l) g= g->parent, l = l->parent;
}
Pseudocode:
node *FindCommonAncestor(node *root, node *node1, node *node2) {
node *current = node1;
node_list temp_list;
temp_list.add(current);
while (current != root) {
current = current.parent;
temp_list.add(current);
}
current = node2;
while (current not in temp_list) {
current = current.parent;
}
return current;
}
If the nodes are definitely part of the same tree, then they'll definitely have a common ancestor (even if it's the root in the worst case). So it will always terminate and there's no error condition to worry about.
The first loop runs n times, where n is the depth of node1, so it's O(n). The second loop runs m times, where m in the depth of node2. The lookup into temp list is (at worst) n. So the second loop is O(m*n), and it dominates, so the function runs in O(m*n).
If you use a good set data structure (e.g., a hash table) for the temp space instead of a list, you can cut the lookup to (typically) O(1), without increasing the cost of adding nodes to temp. This reduces our function time to O(m).
The space requirement is O(n) either way.
Since we don't know n and m ahead of time, let's put it in terms of the total number of nodes in the tree: S. If the tree is balanced, then n and m are each bounded by log_2(S), so the run time is O(log_2(S)^2). Log_2 is pretty powerful, so S would have to get pretty big before I'd worry about the power of 2. If the tree is not balanced, then we lose the log_2 (the tree might actually degenerate into a linked list). So the absolute worst case (when one node is the root and the other is the leaf of a completely degenerate tree) is O(S^2).
hi this will return lowest ancestor node value where root of tree and val1,val2 -> data values for nodes are being passed
int CommonAncestor(node *root, int val1,int val2)
{
if(root == NULL || (! root->left && ! root->right )
return false;
while(root)
{
if(root->data < val1 && root->data < val2)
{
root = root->left;
}
else if(root->data > val1 && root->data > val2)
{
root= root->right;
}
else
return root->data;
}
}
Pre order traversal unless any 1 of the node is met and save the nodes visited uptil now.
Inorder traversal,start saving the nodes when any 1 (of the two provided nodes) node is met,and save the list until the next node is met.
- post order traversal,start saving the nodes when both the nodes hav been visited...
A
B C
D E F G
H I J K L M N O
Suppose H and E are two random nodes.
- ABDH
- HDIBJE
- EBLMENOGCA
Find the first node common in all three...
Here are two approaches in c# (.net) (both discussed above) for reference:
Recursive version of finding LCA in binary tree (O(N) - as at most each node is visited) (main points of the solution is LCA is (a) only node in binary tree where both elements reside either side of the subtrees (left and right) is LCA. (b) And also it doesn't matter which node is present either side - initially i tried to keep that info, and obviously the recursive function become so confusing. once i realized it, it became very elegant.
Searching both nodes (O(N)), and keeping track of paths (uses extra space - so, #1 is probably superior even thought the space is probably negligible if the binary tree is well balanced as then extra memory consumption will be just in O(log(N)).
so that the paths are compared (essentailly similar to accepted answer - but the paths is calculated by assuming pointer node is not present in the binary tree node)
Just for the completion (not related to question), LCA in BST (O(log(N))
Tests
Recursive:
private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode,
int e1, int e2)
{
Debug.Assert(e1 != e2);
if(treeNode == null)
{
return null;
}
if((treeNode.Element == e1)
|| (treeNode.Element == e2))
{
//we don't care which element is present (e1 or e2), we just need to check
//if one of them is there
return treeNode;
}
var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
if(nLeft != null && nRight != null)
{
//note that this condition will be true only at least common ancestor
return treeNode;
}
else if(nLeft != null)
{
return nLeft;
}
else if(nRight != null)
{
return nRight;
}
return null;
}
where above private recursive version is invoked by following public method:
public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
{
var n = this.FindNode(this._root, e1);
if(null == n)
{
throw new Exception("Element not found: " + e1);
}
if (e1 == e2)
{
return n;
}
n = this.FindNode(this._root, e2);
if (null == n)
{
throw new Exception("Element not found: " + e2);
}
var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
if (null == node)
{
throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
}
return node;
}
Solution by keeping track of paths of both nodes:
public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
{
var path1 = new List<BinaryTreeNode>();
var node1 = this.FindNodeAndPath(this._root, e1, path1);
if(node1 == null)
{
throw new Exception(string.Format("Element {0} is not found", e1));
}
if(e1 == e2)
{
return node1;
}
List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
var node2 = this.FindNodeAndPath(this._root, e2, path2);
if (node1 == null)
{
throw new Exception(string.Format("Element {0} is not found", e2));
}
BinaryTreeNode lca = null;
Debug.Assert(path1[0] == this._root);
Debug.Assert(path2[0] == this._root);
int i = 0;
while((i < path1.Count)
&& (i < path2.Count)
&& (path2[i] == path1[i]))
{
lca = path1[i];
i++;
}
Debug.Assert(null != lca);
return lca;
}
where FindNodeAndPath is defined as
private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
{
if(node == null)
{
return null;
}
if(node.Element == e)
{
path.Add(node);
return node;
}
var n = this.FindNodeAndPath(node.Left, e, path);
if(n == null)
{
n = this.FindNodeAndPath(node.Right, e, path);
}
if(n != null)
{
path.Insert(0, node);
return n;
}
return null;
}
BST (LCA) - not related (just for completion for reference)
public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
{
//ensure both elements are there in the bst
var n1 = this.BstFind(e1, throwIfNotFound: true);
if(e1 == e2)
{
return n1;
}
this.BstFind(e2, throwIfNotFound: true);
BinaryTreeNode leastCommonAcncestor = this._root;
var iterativeNode = this._root;
while(iterativeNode != null)
{
if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
{
iterativeNode = iterativeNode.Left;
}
else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
{
iterativeNode = iterativeNode.Right;
}
else
{
//i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
return iterativeNode;
}
}
//control will never come here
return leastCommonAcncestor;
}
Unit Tests
[TestMethod]
public void LeastCommonAncestorTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
bst.Add(e);
bst.Delete(e);
bst.Add(e);
}
for(int i = 0; i < b.Length; i++)
{
var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
Assert.IsTrue(n.Element == b[i]);
var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
Assert.IsTrue(n1.Element == b[i]);
Assert.IsTrue(n == n1);
var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
Assert.IsTrue(n2.Element == b[i]);
Assert.IsTrue(n2 == n1);
Assert.IsTrue(n2 == n);
}
}
加载中,请稍侯......
精彩评论