FastPrepMinimum Root-to-Leaf Cut Cost
Problems/Minimum Root-to-Leaf Cut Cost

Minimum Root-to-Leaf Cut Cost

Google logoGoogle● MediumFULLTIMEINTERNNEW GRADPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report specifies the weighted binary-tree objective, nonnegative costs, fixed original leaves, the child-edge recurrence, and empty/root-only behavior. It does not give a portable array interface or examples; those presentation details are supplied here. The judged core task matches the visible source at about 97%.

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.

A leaf is determined from the original tree: it is a node with no children before any cuts. Cutting an edge may disconnect many original leaves at once. Nodes that become leaves only because of earlier cuts do not add new requirements.

If all four arrays are empty, or if the tree contains only its root, return 0.

Interview follow-up

The primary problem requires nonnegative edge costs. With negative costs, an optimal answer may cut extra edges even after a leaf is already disconnected, so the primary recurrence no longer applies unchanged.

Function

minimumRootLeafCutCost(leftChild: List<Integer>, rightChild: List<Integer>, leftCost: List<Integer>, rightCost: List<Integer>) → long

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 = 11

Below 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.

Example 2

leftChild = [1,2,3,-1]rightChild = [-1,-1,-1,-1]leftCost = [8,3,5,0]rightCost = [0,0,0,0]return = 3

There is one root-to-leaf path. Cutting its middle edge, from node 1 to node 2, costs 3, which is cheaper than cutting either other edge.

Example 3

leftChild = [-1]rightChild = [-1]leftCost = [0]rightCost = [0]return = 0

The root-only case has no edge that can be cut, and the required result is 0.

Constraints

  • 0 <= n <= 2147483647
  • All four arrays have length n.
  • When n > 0, the child indices form one valid binary tree rooted at node 0: every node other than 0 appears exactly once as a child, and every node is reachable from the root.
  • Each child index is -1 or lies between 0 and n - 1.
  • An absent child has matching edge cost 0. A present edge has cost between 0 and 2147483647, inclusive.
  • The sum of all edge costs is at most 2147483647.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public long minimumRootLeafCutCost(List<Integer> leftChild, List<Integer> rightChild, List<Integer> leftCost, List<Integer> rightCost) {
        // Write your code here
    }
}
Checking account…