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 }
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous
post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree
above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.
Hint:
Top-down or bottom-up? Consider both approaches and see which one is more efficient.
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 }