DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

SalahElhossiny
SalahElhossiny

Posted on

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





Enter fullscreen mode Exit fullscreen mode

Top comments (0)

πŸ€” Did you know?

Β 
DEV has a variety of tags to help you find the content you like. Find and follow your favorite tags.