Find cheapest common ancestor in a tree

Coding

You are given a rooted tree where each node has:

• an integer price
• a pointer to its parent (root has parent = null )
• a list of children

Given two distinct nodes a and b from the same tree, find the common ancestor of a and b (including a node as an ancestor of itself) that has the minimum price.

Output

Return the node (or its identifier) that is the cheapest among all common ancestors.

Notes / edge cases

• If a == b , then a is a common ancestor.
• If multiple common ancestors have the same minimum price, you may return any one of them (or specify a tie-breaker such as returning the deepest among them).

Constraints (assume typical interview constraints)

• Up to ~10^5 nodes.
• Tree may be unbalanced.
• Prices can be any integers.

What to discuss

• A brute-force approach and its time complexity.
• An optimal approach for a single query.
• Test cases and edge cases.