CareerCup

This will make use Inorder and Postorder Traversal.
LCA 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

Small correction: This is a BST

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);

// code for finding common ancestor in a BST for two node having minimum values
// code will return the address of the common ancestor
struct node *ancestor(struct node *p)
{
if(p->left->left->left)
ancestor(p->left);
else
return p;
}

(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)

Please correct me,If am missing something,
If its a BST , a common least ancestor will be always top most root right ?

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;