Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Trees (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@kavan3]

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

[@SHIHJUIheh]

This is a really good explanation. It's so much better than my professor's！

[@supriya7720]

Love your explanations. Please do more problems on LinkedLists, Sliding window, Two Pointers etc. I find your explanations much better than Neetcode🙈

[@GregHogg]

Glad to hear it! And I have playlists for all these categories :)

[@niranjanbhat3949]

Good explanation, i suggest u bring more dp and sliding window problems please 😊

[@GregHogg]

Thank you! I've got lots of sliding window, dp is coming up shortly

[@user-jm6gp2qc8x]

Hey Greg, I think O(logN) is correct for time complexity.

[@gaiusjuliuscaesar9296]

Title says problem 236 (LCA of a binary tree) but video is on problem 235 (LCA of a binary SEARCH tree)

[@GregHogg]

Thanks so much for noticing this!

[@philipbrujic4728]

Another approach that would work is adding nonlocal lca in function scope

[@ketkiambekar7607]

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

[@prithvishdoshi1224]

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.