simple solution:
public static Node lca(Node root, Node node1, Node node2) {
if (root == null) return null;
if (node1.val > root.val && node2.val > root.val) return lca(root.right, node1, node2);
else if (node1.val < root.val && node2.val < root.val) return lca(root.left, node1, node2);
else return root;
}
All the test cases are Binary Search Trees. A simple code comparing the nodes can solve this in O(log n). Please add some Binary tree test cases.
This question could use some clarification around expected behavior if the value for v or w isn’t in the tree. Consider a tree 6 4 x 5 x x 8 x x with nodes 3 and 4. The python solution outputs 4, but 3 isn’t a node in the tree. It seems like either the code should return None if the nodes don’t exist, or it should be stated in the problem that we should assume both nodes exist in the tree. Am I misunderstanding?
Yeah - I have this issue as well, it must be assuming that the nodes exist in the tree - I was stuck on this for a while =
But on the other hand, if none of the nodes exists, the code will, correctly, return null - so this assumption is not consistent.
It only returns null if none of the nodes are in the tree, if any one of them are in there, it’ll return that one.
Not the most efficient, but this works and does not assume that the tree contains both of the nodes
def has_node(root: Node, to_search_for: Node) → bool:
if root is None:
return None
if root.val == to_search_for.val:
return True
is_in_left = has_node(root.left, to_search_for)
is_in_right = has_node(root.right, to_search_for)
return is_in_left or is_in_right
def lca(root: Node, node1: Node, node2:Node) → Node:
if root is None:
return None
#if we are node 1 and node 2 exists on left or right, the we are the LCA
if root.val == node1.val:
if has_node(root.left, node2):
return root
if has_node(root.right, node2):
return root
#if we are node 2 and node 1 exists on left or right, then we are the LCA
if root.val == node2.val:
if has_node(root.left, node1):
return root
if has_node(root.right, node1):
return root
#See if we find node1 on the left
node1_on_left = has_node(root.left, node1)
node1_on_right = has_node(root.right, node1)
#If we do not have a node1
if not (node1_on_left or node1_on_right):
return None
node2_on_left = has_node(root.left, node2)
node2_on_right = has_node(root.right, node2)
#If we do not have a node2
if not (node2_on_left or node2_on_right):
return None
#we are LCA if node1 and node two exist on opposite sides
if (node1_on_left and node2_on_right) or (node1_on_right and node2_on_left):
return root
#we are not the LCA, try to find it on the left
lca_on_the_left = lca(root.left, node1, node2)
if lca_on_the_left is not None:
return lca_on_the_left
#didn't find it on the left, try on the right
lca_on_the_right = lca(root.right, node1, node2)
if lca_on_the_right is not None:
return lca_on_the_right
#We do not have an LCA under us
return None
It would be nice if there was type declaration in the function signature. I just spent 10 minutes trying to figure out where my code went wrong, when all I had to do was remove .value from if root.value == node1 or root.value == node2…
would also have been nice to know it’s a binary search tree, not just a binary tree. Video solution and associated LC problem are both BST and guarantee solutions.
For the Javascript solution, if (root === node1 || root === node2) return root; how does this make sense? so we aren’t exploring any deeper in the current node of our subtree if that node is eqal to node1 or node 2? doesn’t this prevent us from observing a case 2 scenario?
Guys, we are re-writing this article with a better explanation very soon. Stay tuned. Thanks 
Here’s my approach:
soln = None
def lca(root, node1, node2):
def dfs(root, node1, node2):
global soln
if root is None:
return 0
left = dfs(root.left, node1, node2)
right = dfs(root.right, node1, node2)
mid = 1 if root.val in [node1.val, node2.val] else 0
if left + right + mid >= 2:
soln = root
return 1 if (mid + left + right > 0) else 0
dfs(root, node1, node2)
return soln
soln = None
def lca(root, node1, node2):
def dfs(root, node1, node2):
global soln
if root is None:
return 0
left = dfs(root.left, node1, node2)
right = dfs(root.right, node1, node2)
mid = 1 if root.val in [node1.val, node2.val] else 0
if left + right + mid >= 2:
soln = root
return 1 if (mid + left + right > 0) else 0
dfs(root, node1, node2)
return soln
How do we format code before we post?
Not as concise, but clearer to understand IMO
def lca(root, node1, node2):
# update all nodes with parents; find p and q, stop when both are found
def add_parent(node, parent, p, q):
if not node: return p, q
node.parent = parent
if node == node1:
p = node
if node == node2:
q = node
if p is None or q is None: # keep DFS going only when either of the nodes is not found
p, q = add_parent(node.left, node, p, q)
p, q = add_parent(node.right, node, p, q)
return p, q
# find lowest shared parent - helper method to build a list of nodes from root to node
def path_to_root(node):
res = []
while True:
res.append(node)
if node.parent == 'root':
break
node = node.parent
return res[::-1]
p, q = add_parent(root, 'root', None, None)
if p is None or q is None: # at least one node is not found
return None
p_path = path_to_root(p)
q_path = path_to_root(q)
# given two lists (paths from root), return their righmost shared element
res = [l for l, r in zip(p_path, q_path) if l == r][-1]
return res
I had 2 ways to do this… one pretty much the same as the answer provided and one using path building
public static TreeNode lca(TreeNode root, TreeNode node1, TreeNode node2, int type) {
switch (type) {
case 1:
return lcaUsingChildKnowledge(root, node1, node2);
default:
return lcaUsingPath(root, node1, node2);
}
}
public static TreeNode<Integer> lcaUsingChildKnowledge(TreeNode<Integer> root, TreeNode<Integer> node1, TreeNode<Integer> node2){
// If either (node1 or node2) is in my left side and the other is in my right side then return myself as I'm the lca
// If my kids pass me up a node them that means either that node is node1/node2 (or it's the lca)... so I should pass that back up
// If I'm either of the nodes... then I should return myself and my ancestor can check its other subtree for presence of the other
// otherwise if I'm not the node and I don't have the node in any of my kids... I should return null
// predicates
// I'm a node, I'm the lca, I'm neither
// my left child is a node, is the lca, is neither
// my right child is a node, is the lca, is either
TreeNode<Integer> result = null;
if(root == null) return result;
if(root.equals(node1) || root.equals(node2)){
// I'm a node... I might be the LCA if one of the below comes back !!
result = root;
}
TreeNode<Integer> leftResult = lcaUsingChildKnowledge(root.left, node1, node2);
if(leftResult != null){
// my left has a node or is an lca
if(result == null) result = leftResult;
}
TreeNode<Integer> rightResult = lcaUsingChildKnowledge(root.right, node1, node2);
if(rightResult != null){
// my right has a node or is an lca
if(leftResult != null) {
// we had a match from right and left... so root must be lca
result = root;
}
else if(leftResult == null && result == null){
// right had a match but nothing else did
result = rightResult;
}
}
return result;
}
public static TreeNode<Integer> lcaUsingPath(TreeNode<Integer> root, TreeNode<Integer> node1, TreeNode<Integer> node2) {
List<TreeNode<Integer>> pathToNode1 = new ArrayList<>(), pathToNode2 = new ArrayList<>();
findPathToNode(root, node1, pathToNode1);
findPathToNode(root, node2, pathToNode2);
int shortestPath = Math.min(pathToNode1.size(), pathToNode2.size());
if(shortestPath == 0) return null;
else{
int i = 0;
for(; i < shortestPath; i++){
if(!pathToNode1.get(i).equals(pathToNode2.get(i))) break;
}
return pathToNode1.get(i-1);
}
}
public static boolean findPathToNode(TreeNode<Integer> node, TreeNode<Integer> nodeToFind, List<TreeNode<Integer>> listToPopulate){
if(node == null) return false;
else if(node.equals(nodeToFind)){
listToPopulate.add(node);
return true;
}
else {
listToPopulate.add(node);
if(findPathToNode(node.left, nodeToFind, listToPopulate) == false && findPathToNode(node.right, nodeToFind, listToPopulate) == false) {
listToPopulate.remove(listToPopulate.size() - 1);
return false;
}
else return true;
}
}
cleaned it up some
public static TreeNode lcaUsingChildKnowledge(TreeNode root, TreeNode node1, TreeNode node2){
// If either (node1 or node2) is in my left side and the other is in my right side then return myself as I’m the lca
// If my kids pass me up a node them that means either that node is node1/node2 (or it’s the lca)… so I should pass that back up
// If I’m either of the nodes… then I should return myself and my ancestor can check its other subtree for presence of the other
// otherwise if I’m not the node and I don’t have the node in any of my kids… I should return null
// predicates
// I’m a node, I’m the lca, I’m neither
// my left child is a node, is the lca, is neither
// my right child is a node, is the lca, is either
if(root == null) return null;
if(root.equals(node1) || root.equals(node2)) return root; // I’m either lca or one of the nodes
TreeNode leftResult = lcaUsingChildKnowledge(root.left, node1, node2);
TreeNode rightResult = lcaUsingChildKnowledge(root.right, node1, node2);
if(leftResult != null && rightResult != null) return root; // I’m the lca!
else if(leftResult != null) return leftResult; // one of my left children is a node (my right returned nothing)
else if (rightResult != null) return rightResult; // one of my right children is a node (my right returned nothing)
else return rightResult; // no matches at all
}
public static TreeNode<Integer> lcaUsingChildKnowledge(TreeNode<Integer> root, TreeNode<Integer> node1, TreeNode<Integer> node2){
// If either (node1 or node2) is in my left side and the other is in my right side then return myself as I'm the lca
// If my kids pass me up a node them that means either that node is node1/node2 (or it's the lca)... so I should pass that back up
// If I'm either of the nodes... then I should return myself and my ancestor can check its other subtree for presence of the other
// otherwise if I'm not the node and I don't have the node in any of my kids... I should return null
// predicates
// I'm a node, I'm the lca, I'm neither
// my left child is a node, is the lca, is neither
// my right child is a node, is the lca, is either
if(root == null) return null;
if(root.equals(node1) || root.equals(node2)) return root; // I'm either lca or one of the nodes
TreeNode<Integer> leftResult = lcaUsingChildKnowledge(root.left, node1, node2);
TreeNode<Integer> rightResult = lcaUsingChildKnowledge(root.right, node1, node2);
if(leftResult != null && rightResult != null) return root; // I'm the lca!
else if(leftResult != null) return leftResult; // one of my left children is a node (my right returned nothing)
else if (rightResult != null) return rightResult; // one of my right children is a node (my right returned nothing)
else return rightResult; // no matches at all
}
Sorry formatting 
public static TreeNode<Integer> lcaUsingChildKnowledge(TreeNode<Integer> root, TreeNode<Integer> node1, TreeNode<Integer> node2){
if(root == null) return null;
if(root.equals(node1) || root.equals(node2)) return root; // I'm either lca or one of the nodes
TreeNode<Integer> leftResult = lcaUsingChildKnowledge(root.left, node1, node2);
TreeNode<Integer> rightResult = lcaUsingChildKnowledge(root.right, node1, node2);
if(leftResult != null && rightResult != null) return root; // I'm the lca!
else if(leftResult != null) return leftResult; // one of my left children is a node (my right returned nothing)
else if (rightResult != null) return rightResult; // one of my right children is a node (my left returned nothing)
else return null; // no matches at all
}
:Facepalm: comment spam… small edit to last 2 lines
Thanks, the explanation is wonderful!