Friday, July 13, 2012

Write a program to find least common ancestor (lca) of 2 nodes in a binary search tree

The approach:-
  1. Starting from the root node.

  2. Check if the node key is between the two provided keys. If so, the current node is the least common ancestor.

  3. If the two provided keys are greater than the current node then recursively search the right sub-tree.

  4. If the two provided keys are less than the current node then recursively search the left sub-tree.

C++ program to find least common ancestor (lca) of 2 nodes in a binary search tree

#include <iostream>
#include <cstdlib>
using namespace std;

// Node class
class Node {
public:
    Node() { mData = -1; mParent = NULL; mLeft = NULL; mRight = NULL; }
    ~Node() {}
    int data() { return mData; }
    void setData(int data) { mData = data; }
    Node* left() { return mLeft; }
    void setLeft(Node* left) { mLeft = left; }
    Node* right() { return mRight; }
    void setRight(Node* right) { mRight = right; }
    Node* parent() { return mParent; }
    void setParent(Node* parent) { mParent = parent; }
private:
    int mData;
    Node* mLeft;
    Node* mRight;
    Node* mParent;
};

// Tree class
class Tree {
public:
    Tree() { mRoot = NULL; }
    ~Tree() {}
    Node* root() { return mRoot; }
    void addNode(int data);
    Node* lca(Node* node, int data1, int data2);

private:
    void addNode(Node* node, int data);

private:
    Node* mRoot;
};

void Tree::addNode(int data) {
    if ( mRoot == NULL ) {
        Node* tmp = new Node();
        tmp->setData(data);
        mRoot = tmp;
    }
    else {
        addNode(mRoot, data);
    }
}

void Tree::addNode(Node* node, int data) {
    if ( data <= node->data() ) {
        if ( node->left() != NULL )
            addNode(node->left(), data);
        else {
            Node* tmp = new Node();
            tmp->setData(data);
            tmp->setParent(node);
            node->setLeft(tmp);
        }
    }
    else {
        if ( node->right() != NULL )
            addNode(node->right(), data);
        else {
            Node* tmp = new Node();
            tmp->setData(data);
            tmp->setParent(node);
            node->setRight(tmp);
        }
    }
}

Node* Tree::lca(Node* node, int data1, int data2) {
    if ( node ) {
        int data = node->data();
        if ( data1 < data && data2 > data )
            return node;
        else if ( data1 > data && data2 > data )
            return lca(node->right(), data1, data2);
        else
            return lca(node->left(), data1, data2);
    }
    return NULL;
}

// Test program
int main() {
    Tree* t = new Tree();
    t->addNode(500);
    t->addNode(300);
    t->addNode(600);
    t->addNode(550);
    t->addNode(700);
    t->addNode(750);
    t->addNode(200);
    t->addNode(150);
    t->addNode(250);
    t->addNode(350);
    t->addNode(800);

    cout << t->lca(t->root(), 150, 350)->data() << endl;

    delete t;
}


Output:-
300

2 comments :

  1. What if the the given Nodes don't even exists?
    What if one of the data equals to the node's data (eg.: 300, 350), then it will return NULL, but the common ancestor is 500.

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top