Skip to content

236. Lowest Common Ancestor of a Binary Tree 👍

Approach 1: Recursive

  • Time: $O(h)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q)
      return root;

    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);

    if (l && r)
      return root;
    return l ? l : r;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
      return root;

    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);

    if (l != null && r != null)
      return root;
    return l == null ? r : l;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
      return root

    l = self.lowestCommonAncestor(root.left, p, q)
    r = self.lowestCommonAncestor(root.right, p, q)

    if l and r:
      return root
    return l or r

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    queue<TreeNode*> q_{{root}};
    unordered_map<TreeNode*, TreeNode*> parent{{root, nullptr}};
    unordered_set<TreeNode*> ancestors;  // p's ancestors

    // iterate until we find both p and q
    while (!parent.count(p) || !parent.count(q)) {
      root = q_.front(), q_.pop();
      if (root->left) {
        parent[root->left] = root;
        q_.push(root->left);
      }
      if (root->right) {
        parent[root->right] = root;
        q_.push(root->right);
      }
    }

    // insert all of p ancestors
    while (p) {
      ancestors.insert(p);
      p = parent[p];  // p becomes nullptr in the end
    }

    // go up from q until meet any of p's ancestors
    while (!ancestors.count(q))
      q = parent[q];

    return q;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Queue<TreeNode> q_ = new ArrayDeque<>(Arrays.asList(root));
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    parent.put(root, null);
    Set<TreeNode> ancestors = new HashSet<>(); // p's ancestors

    // iterate until we find both p and q
    while (!parent.containsKey(p) || !parent.containsKey(q)) {
      root = q_.poll();
      if (root.left != null) {
        parent.put(root.left, root);
        q_.offer(root.left);
      }
      if (root.right != null) {
        parent.put(root.right, root);
        q_.offer(root.right);
      }
    }

    // insert all of p ancestors
    while (p != null) {
      ancestors.add(p);
      p = parent.get(p); // p becomes nullptr in the end
    }

    // go up from q until meet any of p's ancestors
    while (!ancestors.contains(q))
      q = parent.get(q);

    return q;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def lowestCommonAncestor(self, root: Optional[TreeNode], p: Optional[TreeNode], q: Optional[TreeNode]) -> Optional[TreeNode]:
    q_ = deque([root])
    parent = {root: None}
    ancestors = set()  # p's ancestors

    # iterate until we find both p and q
    while p not in parent or q not in parent:
      root = q_.popleft()
      if root.left:
        parent[root.left] = root
        q_.append(root.left)
      if root.right:
        parent[root.right] = root
        q_.append(root.right)

    # insert all of p ancestors
    while p:
      ancestors.add(p)
      p = parent[p]  # p becomes None in the end

    # go up from q until meet any of p's ancestors
    while q not in ancestors:
      q = parent[q]

    return q