Tuesday, December 18, 2012

Find the Immediate Ancestor of a node

There are two ways by which we can find the immediate ancestor of the node . One way is same like Lowest Common Ancestor Problem . The other way is suggested by my friend ,that's almost the same idea . But the style of coding is different . I really liked the second Method .

1st Method:(in C)

struct node * immediateAncestor(struct node *root,struct node *node)
{
if(root==NULL)
return NULL;
if(root->left==node || root->right==node)
return root;
else
{
struct node* left,right;
left=immediateAncestor(root->left,node);
right=immediateAncestor(root->right,node);
return (left!=NULL)?left:right;
}
}

2nd Method:(in C++)

node* ancestor(node *root, node *x)
{
if(root == NULL || x==NULL || root == x)
return NULL;
if(root->left==x || root->right==x)
return root;
return (ancestor(root->left,x)||ancestor(root->right,x));
}

No comments: