Binary Search Tree Lowest Common Ancestor | Dataford Interview Questions

An Atlassian Jira issue index stores issue priorities in a binary search tree. Given the tree's root and two distinct priority values, find their lowest common ancestor, defined as the deepest node that is an ancestor of both values.

Use the binary search tree ordering property to avoid traversing unrelated subtrees. Return the ancestor's integer value. You may assume both target values exist in the tree.

Formal Specification

Implement lowest_common_ancestor(root, p, q).

root is either None or a nested mapping with integer key val and child keys left and right.
p and q are distinct integers contained in the tree.
Return the integer value of their lowest common ancestor.
The tree follows left.val < node.val < right.val for every node.

Constraints

1 <= number of nodes <= 10^5
-10^9 <= node.val, p, q <= 10^9
All node values are unique
Both target values exist in the tree
The tree satisfies the binary search tree ordering property

Function Signature

def lowest_common_ancestor(root, p, q):

Your question is Binary Search Tree Lowest Common Ancestor. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem