Within in the first 3 minutes of your video I figured out why my code wasn't working. Once I did a check for P and for Q separately first to confirm they both exist, my solution started working. All I had to do is check if P or Q doesn't exist and return Null, if they both exist, then I can do the normal "find ancestor" code. But of course this wasn't efficient enough, so thank you for showing me the optimized version
a bit complex, you can just find lca like (lca of BT 1) and get node1 and then perfrom node2 = lca(node1.left) or lca(node1.right) and if both nodes then return node1, else None
Yes. This is the same question I have. Also if P and Q both are found in left subtree, why do we have to still traverse right subtree? That does not seem necessary.
The way that the statement 'return l or r' works is it will return whichever one of those has a value attached to it. So in the example in the video (covering the example where p = 5 and q = 10), it would return the node containing the value of 5.
@@klppdc Because it is not guaranteed that both P and Q will always be found in the left subtree. An algorithm only containing the code to find that would not pass all of the test cases that this question is asking for. So we must make sure that we also cover cases where P and Q are in separate subtrees and where P or Q (or both) do not exist.
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](/img/tr.png)
Wow, the explanation was super clear! Thx, mate!
Thanks! Make sure to subscribe if you haven’t already 😉
Within in the first 3 minutes of your video I figured out why my code wasn't working. Once I did a check for P and for Q separately first to confirm they both exist, my solution started working.
All I had to do is check if P or Q doesn't exist and return Null, if they both exist, then I can do the normal "find ancestor" code.
But of course this wasn't efficient enough, so thank you for showing me the optimized version
a bit complex, you can just find lca like (lca of BT 1) and get node1 and then perfrom node2 = lca(node1.left) or lca(node1.right)
and if both nodes then return node1, else None
Thank you . Your channel videos are super easy to understand.
8:59 sorry I am confused here. If returning 4 or 5 doesn't matter, how would the algorithm make sure to return the correct answer, 5 but not 4?
Yes. This is the same question I have. Also if P and Q both are found in left subtree, why do we have to still traverse right subtree? That does not seem necessary.
The way that the statement 'return l or r' works is it will return whichever one of those has a value attached to it. So in the example in the video (covering the example where p = 5 and q = 10), it would return the node containing the value of 5.
@@klppdc Because it is not guaranteed that both P and Q will always be found in the left subtree. An algorithm only containing the code to find that would not pass all of the test cases that this question is asking for. So we must make sure that we also cover cases where P and Q are in separate subtrees and where P or Q (or both) do not exist.
Wouldn't storing l and r result in an O(N) space complexity? Since the None value also takes space in memory as well.
Thank you for explaining, it was helpful!
Glad you found the video helpful! Make sure to subscribe so you don’t miss other videos coming soon
Great Explanation! Thanks!
Glad you enjoyed the video! Make sure to subscribe so you don’t miss future videos