take In-order(LVR) and pre-order(VLR) traversals of the tree... then as per in-order traversal keep dividing the pre-order in two-half untill u get both the nodes asked at two different sides of the node in consideration. This is the parent node.
node * common(node *root, node *first, node*second) { node *temp = root; if (NULL=root) return NULL; if (first is parent of second) return first if (second is parent of first) return second if (first > second) then swap both of them; /* makes life easier */ while(temp) { if(first->data <= temp->data <= second->data) return temp; } } This is for BST
for Binary Tree we can have parent pointer then this prob reduces to common node between 2 connected linked lists.
somebody_found find_ancestor(tree* root, tree* first, tree* second, tree** ancestor) { somebody_found left = NOBODY_FOUND; somebody_found right = NOBODY_FOUND; somebody_found me = NOBODY_FOUND;
if (!root) return NOBODY_FOUND; if (root->left) left = find ancestor(root->left, fisrt, second, ancestor); if (root->right) right = find_ancestor(root->right, first, second, ancestor);
if (left == ANCESTOR_FOUND || right == ANCESTOR_FOUND) return ANCESTOR_FOUND; if ((left+right == BOTH_FOUND)) { *ancester = root; return ANCESTOR_FOUND; }
if (root == fisrt) me = FIRST_FOUND; if (root == second) me = SECOND_FOUND; if (me+left+right == BOTH_FOUND) { return BOTH_FOUND; }
return me; }
Huh.. the logic looks lot more complex, but actually not so. Its just the way of implementing and i went with the crude way...you may find smarter ways of implementing it..
I have an easy solution: Create a path string for 1st node Create a path string for second node Now compare both of them, the node from which they will start differing is the lowest common ancestor.
I believe , while posting the question, you should have mentioned the "lowest " word, because, in any tree, the root is the common ancestor of all the nodes.
In fact, the solution I suggested, can have a simple implementation for a BST ( although problem does not specifically mention that this binary tree satisfies the BST property.) //Assume the value for first node is less than the value for second node //Assume the binary tree satisfies BST property while(root) { if((root->val > first->val) && (root->val> second->val))root=root->left; if((root->val < first->val) && (root->val< second->val))root=root->right; if((root->val > first->val) && (root->val< second->val))return root;
@sudhanshu ..that way you need extra memory O(n) to keep the path strings.And in case of BST it is really simple that is the highest node that devides them i.e lower one is in the left and the higher one is in the right.
7 comments:
take In-order(LVR) and pre-order(VLR) traversals of the tree...
then as per in-order traversal keep dividing the pre-order in two-half untill u get both the nodes asked at two different sides of the node in consideration.
This is the parent node.
node * common(node *root, node *first, node*second)
{
node *temp = root;
if (NULL=root) return NULL;
if (first is parent of second) return first
if (second is parent of first) return second
if (first > second) then swap both of them; /* makes life easier */
while(temp)
{
if(first->data <= temp->data <= second->data) return temp;
}
}
This is for BST
for Binary Tree we can have parent pointer then this prob reduces to common node between 2 connected linked lists.
Ok the recursive procedure is fairly simple;
typedef enum{
NOBODY_FOUND,
FIRST_FOUND,
SECOND_FOUND,
BOTH_FOUND =FIRST_FOUND+SECOND_FOUND,
ANCESTOR_FOUND,
}somebody_found;
somebody_found find_ancestor(tree* root, tree* first, tree* second, tree** ancestor) {
somebody_found left = NOBODY_FOUND;
somebody_found right = NOBODY_FOUND;
somebody_found me = NOBODY_FOUND;
if (!root) return NOBODY_FOUND;
if (root->left) left = find ancestor(root->left, fisrt, second, ancestor);
if (root->right) right = find_ancestor(root->right, first, second, ancestor);
if (left == ANCESTOR_FOUND || right == ANCESTOR_FOUND) return ANCESTOR_FOUND;
if ((left+right == BOTH_FOUND)) {
*ancester = root;
return ANCESTOR_FOUND;
}
if (root == fisrt) me = FIRST_FOUND;
if (root == second) me = SECOND_FOUND;
if (me+left+right == BOTH_FOUND) {
return BOTH_FOUND;
}
return me;
}
Huh.. the logic looks lot more complex, but actually not so. Its just the way of implementing and i went with the crude way...you may find smarter ways of implementing it..
Hi Surendra,
I still feel your code is a little bit difficult for general public like us to understand. Mat be your level is too high.
I have an easy solution:
Create a path string for 1st node
Create a path string for second node
Now compare both of them, the node from which they will start differing is the lowest common ancestor.
I believe , while posting the question, you should have mentioned the "lowest " word, because, in any tree, the root is the common ancestor of all the nodes.
In fact, the solution I suggested, can have a simple implementation for a BST ( although problem does not specifically mention that this binary tree satisfies the BST property.)
//Assume the value for first node is less than the value for second node
//Assume the binary tree satisfies BST property
while(root)
{
if((root->val > first->val) && (root->val> second->val))root=root->left;
if((root->val < first->val) && (root->val< second->val))root=root->right;
if((root->val > first->val) && (root->val< second->val))return root;
@sudhanshu ..that way you need extra memory O(n) to keep the path strings.And in case of BST it is really simple that is the highest node that devides them i.e lower one is in the left and the higher one is in the right.
Post a Comment