Lowest Common Ancestor in a Binary Search Tree

struct TreeNode{
int data;
TreeNode *left;
TreeNode *right;

TreeNode(int val): data(val), left(NULL), right(NULL){}
};

typedef TreeNode* Tree;

//val1 is the min and val2 is the max element and both are present in the tree
TreeNode *lcabst(Tree t, int val1, int val2)
{
if(!t) return NULL;

if(val1 data && val2 >= t->data)
return t;

else if(val1 data && val2 data)
return lcabst(t->left, val1, val2);

return lcabst(t->right, val1, val2);
}

Advertisements

2 thoughts on “Lowest Common Ancestor in a Binary Search Tree

  1. Was just curious, why this problem was heavily studied by scientists and why do we tend to find more methods to solve it like using suffix trees, segment trees etc when we have a simple solution to it like this one?

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s