Lowest Common Ancestor in a BST: GeeksforGeeks

Problem link: http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

Problem Statement:
Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree. You can assume that the nodes are present in the tree.

Solution Idea:
By the definition of BST, all nodes in the left sub-tree is smaller than the root, and all elements of the right sub-tree is greater than the root. So, if we start from root, if root is in between the input nodes then root is the answer, otherwise both input nodes are part of left sub-tree or both are parts of right sub-tree. We perform this operation recursively.

Solution Gist:

Advertisements

Tagged: , , , , , , ,

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

%d bloggers like this: