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)$


Comment