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;
}
You should mention LCA must be in the tree as the assumption.
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.
it returns null if LCA isn’t in the tree
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 js solution, line 24 should say case 3 right? You’re returning null b/c all the previous cases can no longer apply so you can’t find either a target node or a LCA.
Yeah, looks like typo in internal code documentation, case 4 and 5 already covered in:
case 4 and 5, report target node or LCA back to parent
if left:
return left
if right:
return right
Actually I replied for Python solution, I guess JS also has typo like Python code
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?
figured it out looking at other video explanations and leetcode.
there is important information here not explicitly stated. they are:
1.) each node value is unique
2.) the both target nodes are guaranteed to exist in the tree
if we hit a node that is equal to either node 1 or node 2, it is possible that the other value is in that same node’s subtree, but rather than check, we return this node upward. when we return that node back upward, we do a dfs check for the other side.
if we find the value in the left, but null is returned on the right, then we return left node, because we know it is going to be somewhere in it’s subtree. if we have a node for left and right, we return the node we are currently on, because it is confirmed that the other node cannot exist on left’s subtree because each node value is unique.
to put it briefly, rather than search further underneath the subtree when we find a node match, we return it up and check the other side. if it doesnt exist on the other side, we just return the one node we found because we eliminated the possibility that it could be anywhere else but under the subtree of the match we found.
This was SO helpful, thanks for writing your learning process for others to learn from!
100% with cooperdoon on this one. algo monster, you’re great, but this page needs some work
Too confusing to read and understand. This page solution needs a better explanation with a supporting animation or so.
You don’t need to have unique values because you aren’t checking against values you are checking against nodes. A node that has the same value as another node is not going to be at the same memory address, and therefor will not be the same node.