kaushalgoa
Profile Answers by kaushalgoa

Jan 1st, 2008

int is_greater(int x, int y)
{
      if(x > y)
            return 1;
      else
            return 0;

}

int FindLowestCommonAncestor(node* root,int value1,int value2)
{
      int ret;

              if( (root->data == value1 ) ||(root->data == value2))
                      return -1; /* this means that one of the values is same as root->data*/
              else
              {
                      if( ((is_greater(root->data, value1) && (is_greater(value2, root->data))) ) || ((is_greater(value1, root->data) && (is_greater(root->data ,value2))) ))
                              ret = root->data; /* either value1 or value2 are lower and higher than root->data and vice versa*/
                      else if( is_greater(root->data, value1) && is_greater(root->data,value2) && ( (root->left->data != value1 ) ||(root->left->data != value2)))
                              ret = FindLowestCommonAncestor(root->left,value1,value2); /*Both value1 and value2 are lower than root->data*/
                      else if( is_greater( value1, root->data) && is_greater( value2 , root->data) && ((root->right->data != value1 ) ||(root->right->data != value2)))
                              ret = FindLowestCommonAncestor(root->right,value1,value2); /*Both value1 and value2 are higher than root->data*/
                      else
                            ret = root->data; /* Either root->left->data or root->right->data is equal to one of the values*/


              };

      return ret;
}

// Please correct me if I am wrong. Mail me on kaushalgoa @ gmail . com .

Given the values of two nodes in a binary search tree, write a cprogram to find the lowest common ancestor. You may assume that bothvalues already exist in the tree.The function prototype is as follows:int FindLowestCommonAncestor(node* root,int value1,int value) 20 / 8 22 / 4 12 / 10 14I/P : 4 and 14O/P : 8(Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

One of the solution can be to find out postorder traversal taking each node one by one. This postorder function should return true if both the values (v1 & v2) are found in the postorder traversal of the given node. NOTE: The given tree is a BST.... think over it......

vipin gupta
Profile Answers by vipin gupta Questions by vipin gupta
Aug 3rd, 2007
6
2595

Questions by vipin gupta answers by vipin gupta

Answer

Showing Answers 1 - 6 of 6 Answers

abhimanipal
Profile Answers by abhimanipal

Jan 18th, 2010

The basic idea can be outlined as below:

Start with the root. There can be 3 cases.
1. Both the given nodes are to the left of the root. Then go one level lower on the left side
2. Both the given nodes are to the right of the root. Then go one level lower on the right side
3. One of the node is to the left of the root and the other one is to the right. Then the root is the lowest common ancestor.