IT技術小屋

Lowest Common Ancestor of a Binary Search Tree (BST)

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

       _______6______

      /              \

   ___2__          ___8__

  /      \        /      \

  0      _4       7       9

        /  \

        3   5

Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. 

But how about LCA of nodes 2 and 4? Should it be 6 or 2?

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between 

two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a 

node to be a descendant of itself).” Since a node can be a descendant of itself, the LCA of 2 and 

4 should be 2, according to this definition.

Hint:

A top-down walk from the root of the tree is enough.

 1 public class LowestCommonAncestorOfaBinarySearchTree {
 2     public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
 3         if (root == null || p == null || q == null)
 4             return null;
 5         if (Math.max(p.val, q.val) < root.val)
 6             return LCA(root.left, p, q);
 7         if (Math.min(p.val, q.val) > root.val)
 8             return LCA(root.right, p, q);
 9         return root;
10     }
11 }

 1 public class LowestCommonAncestorOfBinaryTree {
 2     public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
 3         if (root == null)
 4             return null;
 5         if (root == p || root == q)
 6             return root;
 7         TreeNode left = LCA(root.left, p, q);
 8         TreeNode right = LCA(root.right, p, q);
 9         if (left != null && right != null)
10             return root;
11         return left != null ? left : right;
12     }
13 }