Minimum Root-to-Leaf Cut Cost
GoogleFULLTIMEPHONE SCREENProblem statement
You are given a rooted binary tree whose edges have nonnegative integer costs. Choose a set of edges to cut so that the root is disconnected from every leaf of the original tree. Return the minimum possible sum of the cut-edge costs.
The tree is encoded by four arrays of equal length n. Node 0 is the root. For each node i, leftChild[i] and rightChild[i] are its child indices, or -1 when that child is absent. When a child is present, the matching entry in leftCost or rightCost is the cost of that edge; when it is absent, the matching cost is 0.
Examples
Example 1
leftChild = [1,3,5,-1,-1,-1,-1]rightChild = [2,4,6,-1,-1,-1,-1]leftCost = [4,1,6,0,0,0,0]rightCost = [7,5,2,0,0,0,0]return = 11Below node 1, cutting both leaf edges costs 1 + 5 = 6, so cutting the root-to-1 edge for 4 is cheaper. Below node 2, the leaf edges cost 6 + 2 = 8, so cutting the root-to-2 edge for 7 is cheaper. The minimum total is 4 + 7 = 11.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.