An Interest In:
Web News this Week
- March 21, 2024
- March 20, 2024
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
August 12, 2022 09:44 am GMT
Original Link: https://dev.to/salahelhossiny/lowest-common-ancestor-of-a-binary-search-tree-16n5
Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root == None: return None node = root while node: if node.val < p.val and node.val < q.val: node = node.right if node.val > p.val and node.val > q.val: node = node.left else: break return node
Original Link: https://dev.to/salahelhossiny/lowest-common-ancestor-of-a-binary-search-tree-16n5
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To