Lowest Common Ancestor in Pedigrees | Dataford Interview Questions

Given a binary tree representing historical pedigree structures at Ancestry, write a function to find the lowest common ancestor of two nodes. Represent each node as a dictionary with value, left, and right keys; missing children are None. The function receives the root and the unique values of two existing nodes, and returns the value of their lowest common ancestor. Use a single traversal and do not modify the tree.

Constraints

1 <= number of nodes <= 1,000
Node values are unique integers
Both target values exist in the tree
The two target values are distinct
The input is a valid binary tree

Function Signature

def lowest_common_ancestor(root, p, q):

Your question is Lowest Common Ancestor in Pedigrees. 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

Constraints

1 <= number of nodes <= 1,000
Node values are unique integers
Both target values exist in the tree
The two target values are distinct
The input is a valid binary tree

Function Signature

def lowest_common_ancestor(root, p, q):

Your question is Lowest Common Ancestor in Pedigrees. 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.