devteampentagon · January 30, 2017 20:20
diff --git a/Lowest Common Ancestors in a Binary Tree [Method - 1].cpp b/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;
 }
	#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;
	}