Last active
March 23, 2020 14:46
-
-
Save nma/237f6b6737bb4abfbcc581d728f416ee to your computer and use it in GitHub Desktop.
LCA algorithm in a BST
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# n1.data <= n2.data | |
def find_lca(tree: BstNode, n1: BstNode, n2: BstNode) -> Optional[BstNode]: | |
while tree: | |
# both left and right child are greater than current node | |
if n1.data > tree.data and n2.data > tree.data: | |
tree = tree.right | |
# both left and right child are less than the current node | |
elif n1.data < tree.data and n2.data < tree.data: | |
tree = tree.left | |
# first node that contains n1 and n2 on either child or are equivalent | |
else: | |
return tree | |
return tree |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment