Find least common ancestor (lca) of 2 nodes in a binary search tree

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