General Lowest Common Ancestor | Dataford Interview Questions

Lowest Common Ancestor

Asked in the Coding Round stage. Given a binary tree with unique integer values and two existing target values, return the value of their lowest common ancestor.

The tree is represented recursively as [value, left, right], where an empty child is null. Implement lowest_common_ancestor(root, p, q).

Examples

[3,[5,[6,null,null],[2,[7,null,null],[4,null,null]]],[1,[0,null,null],[8,null,null]]], p=5, q=1 returns 3.
The same tree with p=5, q=4 returns 5.

Constraints

1 <= nodes <= 10^5
Values are unique; both targets exist; p != q.

Constraints

1 <= number of nodes <= 10^5
Each node value is a unique integer
Both target values exist in the tree
p != q
The tree may be unbalanced

Function Signature

def lowest_common_ancestor(root, p, q):

Your question is General 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