In graph theory and computer science, the lowest common ancestor (LCA) of two nodes is the lowest node that has both of them as descendants.

Let’s take an example:

`LCA(5, 1) => 3` LCA(5, 4) => 5 LCA(5, 0) => 3 LCA(6, 4) => 5

Approach #1 : Recursive Algorithm There are three scenarios for nodes `w`

, `v`

:

There is another node `p`

is LCA of `w`

and `v`

`w`

is in the right subtree of `v`

(or `v`

is in the right subtree of `w`

)
`w`

is in the left subtree of `v`

(or `v`

is in the left subtree of `w`

)
So we can use a recursive algorithm to find the LCA of left subtree and LCA of right subtree.

class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL ) return root; if (right != NULL ) return right; return left; } };

Time complexity: O(N)

Approach #2 : Iterative algorithm with Map and Set We can a `stack`

to traverse the binary tree and use a `map`

record the parent of each node. With this `map`

we could build a `set`

contains all parents of w , and check the parents of v from bottom to top, return the first common parent.

#include <iostream> #include <set> #include <map> #include <stack> using namespace std ;class Solution {public : TreeNode* lowestCommonAncestor (TreeNode* root, TreeNode* p, TreeNode* q) { stack <TreeNode*> stack ; map <TreeNode*, TreeNode*> parents; set <TreeNode*> parents_set; stack .push(root); while (!stack .empty()) { TreeNode* cur = stack .top(); stack .pop(); if (cur->left) { stack .push(cur->left); parents[cur->left] = cur; } if (cur->right) { stack .push(cur->right); parents[cur->right] = cur; } } TreeNode* t = p; while (t != root) { parents_set.insert(t); t = parents[t]; } t = q; while (t != root) { if (parents_set.count(t)) { return t; } t = parents[t]; } return root; } };