MediumLeetCode #235Trees

Lowest Common Ancestor of BST

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Constraints

The number of nodes in the tree is in the range [2, 10^5], All Node.val are unique

Examples

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

Solution

Approach

Use BST property: if both p and q are smaller, go left; if both are larger, go right; otherwise current node is LCA.

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None

Complexity

Time:O(h)

Space:O(1)

Hints

1.Use BST property
2.If both nodes are on same side, continue that direction
3.Split point is the LCA

Asked at

Google