You could also just have the search function return a TreeNode which is the LCA we are looking for. So: def search(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: if not root: return None if p.val < root.val and q.val < root.val: return search(root.left, p, q) elif p.val > root.val and q.val > root.val: return search(root.right, p, q) else: return root
Thanks for the simple explanation. I do have a question about why lca is a list and not a variable. Can you please point me to more explanation about lists being 'proper global variables'? Thanks
The reason for using a list instead of a single value has to do with how Python handles mutable and immutable types. When you pass a list (which is mutable) to a function or reference it within a class, any changes made to the list (like appending or modifying its elements) will persist outside the function. This makes it act more like a "global" variable that can be updated from anywhere in the class. If you were to use lca = root (which is immutable), any attempt to modify var inside the method would create a new local variable, and var outside the method would remain unchanged.
![LOWEST COMMON ANCESTOR OF A BINARY TREE III [PYTHON]](http://i.ytimg.com/vi/vZxxksAP8yk/mqdefault.jpg)
Master Data Structures & Algorithms For FREE at AlgoMap.io!
You could also just have the search function return a TreeNode which is the LCA we are looking for. So:
def search(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root:
return None
if p.val < root.val and q.val < root.val:
return search(root.left, p, q)
elif p.val > root.val and q.val > root.val:
return search(root.right, p, q)
else:
return root
This is a really good explanation. It's so much better than my professor's！
Love your explanations. Please do more problems on LinkedLists, Sliding window, Two Pointers etc. I find your explanations much better than Neetcode🙈
Glad to hear it! And I have playlists for all these categories :)
Good explanation, i suggest u bring more dp and sliding window problems please 😊
Thank you! I've got lots of sliding window, dp is coming up shortly
Thanks for the simple explanation. I do have a question about why lca is a list and not a variable. Can you please point me to more explanation about lists being 'proper global variables'? Thanks
The reason for using a list instead of a single value has to do with how Python handles mutable and immutable types.
When you pass a list (which is mutable) to a function or reference it within a class, any changes made to the list (like appending or modifying its elements) will persist outside the function. This makes it act more like a "global" variable that can be updated from anywhere in the class.
If you were to use lca = root (which is immutable), any attempt to modify var inside the method would create a new local variable, and var outside the method would remain unchanged.
Another approach that would work is adding nonlocal lca in function scope
Hey Greg, I think O(logN) is correct for time complexity.
Title says problem 236 (LCA of a binary tree) but video is on problem 235 (LCA of a binary SEARCH tree)
Thanks so much for noticing this!