Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.

Example:

6
/ \
2 8
/ \ / \
1 4 7 9

The LCA of nodes 2 and 8 is 6.

The LCA of nodes 2 and 4 is 2. (According the definition in Wikipedia)

**Thoughts:**

There’s only four cases you need to consider:

1. Both nodes are to the left of the tree, so the LCA must be in its left subtree.

2. Both nodes are to the right of the tree, so the LCA must be in its right subtree.

3. One node is on the left while the other is on the right, the current node must be the LCA.

4. When the current node equals to either of the two nodes, this node must be the LCA.

**Code:**

public static TreeNode BST_LCA(TreeNode root, int a, int b){
if(root==null)
return null;
if(root.value>a && root.value>b){ //LCA is in left subtree
return BST_LCA(root.left, a, b);
}else if(root.value<a && root.value<b){ //LCA is in right subtree
return BST_LCA(root.right, a, b);
}else{ //root.data==a || root.data==b || root.data in between a and b
return root;
}
}

References:

http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html

http://www.geeksforgeeks.org/archives/1029

### Like this:

Like Loading...

*Related*