Lowest Common Ancestor of a Binary Tree

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

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).”

  1.         _______3______
  2.        /              \
  3.     ___5__          ___1__
  4.    /      \        /      \
  5.    6      _2       0       8
  6.          /  \
  7.          7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.     if (root == null || root == p || root == q)
  13.       return root;
  15.     TreeNode left = lowestCommonAncestor(root.left, p, q);
  16.     TreeNode right = lowestCommonAncestor(root.right, p, q);
  18.     if (left != null && right != null)
  19.       return root;
  20.     else
  21.       return left != null ? left : right;
  22.   }
  23. }