Reference: LeetCode EPI 14.4
Difficulty: Easy

Problem

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

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the BST.

Example: 

1
2
3
4
5
6
7
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Analysis

Methods:

  1. Recursion
    • Start traversing the tree from the root node.
    • If both the nodes p and q are in the right subtree, then continue the search with right subtree.
    • Same for left subtree.
    • If above steps are not true, it means that we have found the node which is common to node p‘s and q‘s subtrees.
    • Bad Code:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
          return null;
        }
        // branching
        if (p.val < root.val && q.val > root.val) {
          return root;
        }
        if (p.val > root.val && q.val < root.val) {
          return root;
        }
        // other cases
        if (p.val == root.val || q.val == root.val) {
          return (p.val == root.val) ? p : q;
        }
        if (p.val < root.val && q.val < root.val) {
          return lowestCommonAncestor(root.left, p, q);
        } else {
          return lowestCommonAncestor(root.right, p, q);
        }
      }
  • Better code: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null) {
        return null;
      }
      if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
      } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
      } else {
        return root;
      }
    }
    Time: $O(h)$
    Space: $O(h)$
  1. Iteration
    • Use $O(1)$ space.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
          if (p.val < root.val && q.val < root.val) {
            root = root.left;
          } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
          } else {
            return root;
          }
        }
        return null;
      }
      Time: $O(h)$
      Space: $O(1)$