Find cheapest common ancestor in a tree
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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.
Quick Answer: This question evaluates understanding of tree data structures and ancestor concepts (such as lowest common ancestor) along with algorithmic skills for aggregating node attributes like minimum values, situating it in the Coding & Algorithms domain and testing practical application backed by conceptual understanding of ancestor relationships.
You are given a rooted tree with nodes labeled from 0 to n - 1. The tree is represented by a parent array, where parent[i] is the parent of node i and the root has parent[i] = -1. Each node also has an integer price given by prices[i]. For two nodes a and b, return the identifier of the common ancestor of both nodes that has the minimum price. A node is considered an ancestor of itself. If multiple common ancestors have the same minimum price, return the deepest one (the one farthest from the root). A brute-force approach may compare ancestor chains directly, but you should aim for an O(h) solution for a single query, where h is the tree height.
Constraints
- 1 <= n == len(parent) == len(prices) <= 10^5
- The input forms a valid rooted tree with exactly one root
- -10^9 <= prices[i] <= 10^9
- 0 <= a, b < n
- a and b belong to the same tree and may be equal
Examples
Input: ([-1, 0, 0, 1, 1, 2, 2], [10, 5, 8, 7, 2, 6, 1], 3, 4)
Expected Output: 1
Explanation: The common ancestors of nodes 3 and 4 are 1 and 0. Their prices are 5 and 10, so node 1 is the cheapest.
Input: ([-1, 0, 0, 1, 1, 2, 2], [10, 5, 8, 7, 2, 6, 1], 5, 6)