Lowest Common Ancestor of a Binary Search Tree (BST)

/*
Lowest Common Ancestor of a Binary Search Tree (BST)
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html

unpolished, non-factored, naive code
*/

#include <iostream>
#include <vector>

using namespace std;

struct node
{
    int val;
    node *left;
    node *right;
    node(int v):val(v), left(NULL), right(NULL){};
};

void topdown(node *root, node *n1, node *n2, node*& res)
{    
    if (!root|| res || !n1 || !n2) return;
    
    if (root->val > n1->val) //root is greatest
    {
        topdown(root->left, n1, n2, res);
    }
    else if (root->val < n2->val) //root is smallest
    {
        topdown(root->right, n1, n2, res);
    }
    else if (root->val < n1->val && root->val > n2->val) //root is in between
    {
        res = root;
    }
    else if (root->val == n1->val)
    {
        if (root == n1)
            res = root;
        else
            topdown(root->left, n1, n2, res);
    }
    else if (root->val == n2->val)
    {
        if (root == n2)
            res = root;
        else
            topdown(root->right, n1, n2, res);
    }
    
}

void topdown_fun(node *root, node *n1, node *n2, node*& res)
{
    (n1->val > n2->val) ? topdown(root, n1, n2, res): topdown(root, n2, n1, res);    
}

int main()
{
    node *root = new node(4);
    node *rleft = new node(2);
    node *rright = new node(5);
    node *rrleft = new node(1);
    node *rrright = new node(3);
    
    root->left  = rleft;
    root->right = rright;
    
    rleft->left  = rrleft;
    rleft->right = rrright;
    
    node *res = NULL;
    
    topdown_fun(root, rrright, rrleft, res);
    
    cout << res->val << endl;
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s