• Time:O(h)
• Space:O(h)

## C++

``````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;
}
};
``````

## JAVA

``````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;
}
}
``````

## Python

``````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
``````

• Time:O(n)
• Space:O(n)

## C++

``````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;
}
};
``````

## JAVA

``````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) {
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;
}
}
``````

## Python

``````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: