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.
Here is an example, given a Binary Search Tree:

What’s Binary search tree
Binary search tree have two properties:
 The value of right child is greater than node’s value
 The value of left child is less than node’s value
Approach #1: Recursive Algorithm
If we traverse each node of binary search tree and comparing the values of p
, q
and current node’s value, there are four scenarios:
 current node is NULL, we will return NULL as result
 root’s value is in the range of values of
p
andq
, root is the lowest common ancestor
 root’s value is less than
p
andq
, then lowest common ancestor will be in the left subtree
root’s value is greater than
p
andq
, then the lowest common ancestor will be the right subtree.Time Complexity: O(N)
Space Complexity: O(N) for recursion stack.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL  p == NULL  q == NULL)
return NULL; // scenario #1
if((p>val <= root>val && root>val <= q>val) 
(p>val >= root>val && root>val >= q>val))
return root; // scenario #2
if(p>val < root>val && q>val < root>val) {
return lowestCommonAncestor(root>left, p, q); // scenario #3
}
if(p>val > root>val && q>val > root>val) {
return lowestCommonAncestor(root>right, p, q); // scenario #4
}
return NULL;
}
};
Approach #2: Iterative Algorithm
Iterative algorithm works similarly to the recursive algorithm, but we don’t need a stack
to backtrace search. In fact, we only need to find the first node, which p
and q
begin to split, one of them is in this node’s left subtree, and the other is in the right subtree.
This algorithm is somehow similar to binary search
.
Time Complexity: O(N)
Space Complexity: O(1)

When the tree is not a binary search tree, but only a binary tree. The solution would be more complex. Please refer to Lowest Common Ancestor Of A Binary Tree.