Print all possible root-to-leaf paths in a binary tree
August 22, 2012
Number Series Question
August 22, 2012

Lowest Common Ancestor in Binary Search Tree

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

12 Comments

  1. Steven says:

    Does this algorithm work?
    For a = 1 and b = 4 it returns NULL instead 5.

  2. hello says:

    it should return 5

  3. Sophia Feng says:

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

  4. Greg Skinner says:

    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)

  5. Alex says:

    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].

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *