## Amazon Interview Question

Applications Developers**Country:**India

**Interview Type:**In-Person

```
int leastCommanAncestor(struct node* root, int n1, int n2)
{
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
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);
}
```

```
void min_common_ancestor(Node* n, int a, int b, bool& has_a, bool& has_b, int& min_ca) {
if (!n) return;
if (n->val == a) { has_a = true; return; }
if (n->val == b) { has_b = true; return; }
min_common_ancestor(n->left, a, b, has_a, has_b, min_ca);
min_common_ancestor(n->right, a, b, has_a, has_b, min_ca);
if (has_a && has_b) min_ca = min(min_ca, n->val);
}
int min_ca = numeric_limits<int>::max();
min_common_ancestor(root, a, b, false, false, min_ca);
```

Better formatted:

```
void min_common_ancestor(Node* n, int a, int b, bool& has_a, bool& has_b, int& min_ca) {
if (!n) return;
if (n->val == a) { has_a = true; return; }
if (n->val == b) { has_b = true; return; }
min_common_ancestor(n->left, a, b, has_a, has_b, min_ca);
min_common_ancestor(n->right, a, b, has_a, has_b, min_ca);
if (has_a && has_b) min_ca = min(min_ca, n->val);
}
int min_ca = numeric_limits<int>::max();
min_common_ancestor(root, a, b, false, false, min_ca);
```

(least common ancestor(LST) follows the bst rules i.e

if n1, n2 are the two numbers then there exist a LST (n) with this property

n1<n<n2 )

--------------------

Algorithm: LST

input:root, n1,n2

output: least common ancestor

LST(root,n1,n2)

if(root = null)

`return 0`

else

`if (n1<root.value and root.value<n2)`

`return root.value`

`if(n1<root.value and n2<root.value`

`return LST(root.left,n1,n2)`

`if(n1>root.value and n2>root.value`

`return LST(root.right,n1,n2)`

Am I getting smthing wrong here. As far as I understand it should be a simple code.

node* leastValueNode = FindMinimum(root);

if (leastValueNode->Right != null)

return leastValueNode;

else if (leastValueNode->Parent != null) // Why? Because the leastValueNode has to be the left child.

return leastValueNode->Parent;

return leastValueNode;

This will make use Inorder and Postorder Traversal.

- Palak Modi August 27, 2012LCA ALGO(Int x, Int y)

1. Perform Inorder Traversal

2. Perform Postorder Traversal

3. Let A be the list of all elements between x and y in inorder traversal,

4. In the postorder traversal, find which element in A comes last that element is Least Common Ancestor.

* Since in inorder Left->Root->right and in Postorder Left->Right->Root