Lowest Common Ancestor in a Binary Search Tree

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

Advertisements

About chesterli0130

Think more
This entry was posted in Trees & Graphs. Bookmark the permalink.

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