Aug 222012
 

In a Binary Search Tree, you are given the values of two nodes. Write a code which will return the Lowest Common Ancestor of both the nodes.

For Example: If the BST is as shown on the right and Nodes are 4 and 8,

The output should be: 5

4 and 8 has two common ancestors 5 and 10. But the lowest one is 5.

Solution:

Lowest Common Ancestor will be the Node which is ancestor to the nodes and whose value lies between the two nodes. 

For any two nodes in a BST, there is one and only one common ancestor whose value will be between the two nodes (i.e less than one and greater than the other). 

Algorithm:

FUNCTION FindCommonAncestor(Node * root, int a, int b)
    IF (value_at_root < a AND value_at_root > b) OR (value_at_root < b AND value_at_root < a) 
        RETURN root 
    ELSE 
        IF (value_at_root < a AND value_at_root < b) 
            RETURN FindCommonAncestor(root->left_sub_tree, a, b) 
        ELSE 
            RETURN FindCommonAncestor(root->right_sub_tree, a, b)

Code:

    /**
     *  Return the Least Common Ancestor (LCA) of Nodes with values a and b
     */   
    Node* commonAncestor(Node* root, int a, int b)
    {
        // case when LCA doesn't exist
        if(root == NULL || root->data == a || root->data == b)
            return NULL; 

        if( (root->data > a && root->data < b) || (root->data > b && root->data < a) )
            return root;

        // LCA will be on the LEFT sub-tree
        if(root->data > a && root->data > b)
            return commonAncestor(root->lptr, a, b);

        // LCA will be on the RIGHT sub-tree
        if(root->data < a && root->data < b)
            return commonAncestor(root->rptr, a, b);
    }

  11 Responses to “Lowest Common Ancestor in Binary Search Tree”

Comments (11)
  1. public void listar(int valorClave1, int valorClave2)throws IOException, volcará por la salida
    estándar la información de los registros del archivo de datos cuyo campo numReg se encuentre
    en el intervalo [valorClave1, valorClave2] (ambos inclusive), ordenados por el campo numReg.
    En la implementación de este método se deberá evitar visitar páginas del árbol B que con toda
    seguridad NO contienen claves que se encuentren dentro del intervalo [valorClave1,
    valorClave2].

  2. Shouldn't the first IF statement of the Algorithm be:

    IF (value_at_root < a AND value_at_root > b) OR (value_at_root > a AND value_at_root < b)

  3. In the Algorithm part, IF (value_at_root < a AND value_at_root < b) and ELSE should be switched

  4. it should return 5

  5. Does this algorithm work?

    For a = 1 and b = 4 it returns NULL instead 5.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)