Lowest Common Ancestors in a Binary Tree [Method - 1]

Lowest Common Ancestors in a Binary Tree [Method - 1].cpp

#include <bits/stdc++.h>

#define MEM(a,b) memset((a),(b),sizeof(a))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MIN3(a,b,c) MIN(MIN(a,b),c)
#define MIN4(a,b,c,d) MIN(MIN(MIN(a,b),c),d)
#define In freopen("In.txt", "r", stdin);
#define Out freopen("out.txt", "w", stdout);

#define i64 long long
#define u64 long long unsigned
#define INF (1<<28)

#define sz 100

using namespace std;

struct Node
{
    int data;
    struct Node* left;
    struct Node * right;
};

Node* getNewNode(int data)
{
    //Create and return new node
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insert(Node* rootPtr,int data)
{
    // base case--we have reached an empty tree and need to insert our new
    // node here
    if(rootPtr == NULL)
        rootPtr = getNewNode(data);
    else
    {
        // decide whether to insert into the left subtree of the right subtree
        // depending on the value of the node

        // build a new tree from rootPtr->left, but add the data
        // replace the existing rootPtr->left pointer with a pointer
        // to the new tree. We need to set the rootPtr->left pointer
        // in case rootPtr->left is NULL. (If it is not NULL,
        // rootPtr->left won't actually change but it doesn't hurt to
        // set it.)

        if(data <= rootPtr->data)
            rootPtr->left = insert(rootPtr->left,data);
        // Insertion into the right is exactly symmetric to insertion
        // into the left
        else rootPtr->right = insert(rootPtr->right,data);

    }
    return rootPtr;
}

int pathFinder(Node *root, vector<int> &paths, int n)
{

    if(root == NULL)
        return false;

    // insert the current path to the list
    paths.push_back(root->data);

    //check either the number is the root
    if(root->data == n)
        return true;

    // call recursively the left child for the number
    if(pathFinder(root->left,paths,n))
        return true;
    // call recursively the left child for the number
    if(pathFinder(root->right,paths,n))
        return true;

    // if the n is not in the tree just
    // pop the last path inserted
    // into the list
    paths.pop_back();
    return false;

}

int LCA(Node *root, int n, int m)
{
    vector<int>  paths1,paths2;

    // find paths for n
    bool nFinder = pathFinder(root,paths1,n);
    // find paths for m
    bool mFinder = pathFinder(root,paths2,m);


    // if any one of them missing then it's not possible
    // to find ancestor
    if(!nFinder || !mFinder)
        return -1;

    // just go through the paths until paths between
    // n and m are not equal
    // return the last same path they shared
    // form the root
    int ind;
    for(ind = 0; ind<paths1.size() && ind<paths2.size(); ind++)
    {
        if(paths1[ind]!=paths2[ind])
            break;
    }
    paths1.clear();
    paths2.clear();
    return paths1[ind-1];
}


int main()
{

    /* Example Binary Search Tree

                7
    		   / \
    		  3   9
    		 / \   \
    		2   4   10
    */

    Node* root;
    root = NULL;

    //test data
    // Inserting the tree

    root = insert(root,40);
    root = insert(root,20);
    root = insert(root,30);
    root = insert(root,25);
    root = insert(root,35);
    root = insert(root,10);
    root = insert(root,5);
    root = insert(root,15);
    root = insert(root,1);
    root = insert(root,80);
    root = insert(root,60);
    root = insert(root,100);




    cout << LCA(root,1,25) << endl;
    cout << LCA(root,2,4) << endl;


    return 0;
}