# 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 q_{{root}}; unordered_map parent{{root, nullptr}}; unordered_set 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 q_ = new ArrayDeque<>(Arrays.asList(root)); Map parent = new HashMap<>(); parent.put(root, null); Set 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