# 8ms java. Not the most elegant algo out there but

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;

Deque<TreeNode> path = new ArrayDeque<TreeNode>();

// find the path, or all the ancestors, from root to one of the nodes, in this case, p
TreeNode temp = root;
while(temp != null && temp.val != p.val) {
if(p.val < temp.val) {
temp = temp.left;
} else {
temp = temp.right;
}
}
// adding itself to path in case of p is ancestor of q itself

// backtrack the path to find the ancestor for q.
// Since the path contains all p's ancestors, so once we find q's ancestor it is the common ancestor of p and q.
// Since it's backtracking, so it is the LCA
while(!path.isEmpty()) {
temp = path.removeLast();
if(isAncestor(temp, q)) return temp;
}

return root;
}

public boolean isAncestor(TreeNode temp, TreeNode q) {
while(temp != null) {
if(q.val == temp.val) return true;
else if(q.val < temp.val) temp = temp.left;
else temp = temp.right;
}
return false;
}
}
``````

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