Synopsys R&D Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
The code seems to need some modifications. The recursive problem should end (or at least save the Node) when the first time"if(left != null && right != null)" is true. This is the LCA node. If you continue to "return root", the code will always return the "actual" root node.
The following is a modified version:
int recursive (struct node *curr, struct node *A, sturct node *B) {
int total;
if (curr==NULL) return 0;
if ((curr->left==A && curr->right==B) || (curr->left==B && curr->right==A))
{
/* found LCA, save the node*/
return 2;
}
if (curr->left==A || curr->right==B) return 1;
else {
total = recursive(curr->left) + recursive(curr->right);
if (total==2) {
/* found LCA, save the node*/
return 2;
}
else return total;
}
Make two linked lists, one for each node.
LinkedList* la,lb; //initialize.
Node* n;
n=a;
while(n!=root)
{
la.pushAtFront(n);
n=n.parent;
}
n=b;
while(n!=root)
{
lb.pushAtFront(n);
n=n.parent;
}
After doing this, both lists' will represent paths from root to these nodes. traverse and see where this path forks.
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}
public Node LCA(Node root, Node a, Node b){
- wqhrock October 18, 2012if(root == null || a == null || b = null) return null;
if(root == a || root == b) return root;
Node left = LCA(root.left, a, b);
Node right = LCA(root.right, a, b);
if(left == null && right == null) return null;
if(left != null && right != null) return root;
if(left == null) return right;
else return left;
}