# 236. Lowest Common Ancestor of a Binary Tree

• We can find the lowest common ancestor of a Binary Tree in three ways.
Method 1: Find the paths to both the nodes p and q. Then compare the paths to find the first diffrence. The node beofre the first difference is the common ancestor.
"""
class Solution {

``````    private List<TreeNode> path1 = new ArrayList<>();
private List<TreeNode> path2 = new ArrayList<>();

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

path1.clear();
path2.clear();
return findLCAInternal(root, p, q);

}

private TreeNode findLCAInternal(TreeNode root, TreeNode n1, TreeNode n2) {

if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
//System.out.println((path1.size() > 0) ? "n1 is present" : "n1 is missing");
//System.out.println((path2.size() > 0) ? "n2 is present" : "n2 is missing");
return null;
}

int i;
for (i = 0; i < path1.size() && i < path2.size(); i++) {
//  System.out.println(path1.get(i) + " " + path2.get(i));
if (!path1.get(i).equals(path2.get(i)))
break;
}

return path1.get(i-1);
}

private boolean findPath(TreeNode root, TreeNode n, List<TreeNode> path)
{
if (root == null) {
return false;
}

if (root == n) {
return true;
}

if (root.left != null && findPath(root.left, n, path)) {
return true;
}

if (root.right != null && findPath(root.right, n, path)) {
return true;
}

path.remove(path.size()-1);

return false;
}
``````

}
"""

Method 2 : using Recurssion. O(n) time and no extra space.
"""
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

``````    /* Efficient recurssive solution without extra space  O(n) TC
* Go through the entire tree once, if p is found return p or return null
* the node with has both left and right not null is the ancestor
*/

if(root == null) return null;

// If any of p or q are root return that
if(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;

return (left!=null)?  left : right;
}
``````

"""
Method 3: Traverse the tree using BFS. After p and q are on same level move up until you find common ancestor. Using HashMap to store the current pointer and parent, and queue for bfs. Later create a ancestor set to store all the ancestors of p. Then find the common ancestor of p and q.
"""
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

``````    /* Using HashMap to store the parents and
find the intersection */

// store current node and parent
Map<TreeNode, TreeNode> parent = new HashMap();
// queue for bfs

parent.put(root, null);

while(!parent.containsKey(p)|| !parent.containsKey(q)) {
TreeNode node = queue.poll();
if(node.left != null) {
parent.put(node.left, node);
}
if(node.right != null) {
parent.put(node.right, node);
}
}
// store the set of parents of p
Set<TreeNode> ancestors = new HashSet<>();
while(p != null) {
p = parent.get(p);
}
// Just check when p and q can intersect
while(!ancestors.contains(q)) {
q = parent.get(q);
}
return q;
}
``````

"""

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.