Google SWE Intern(Stipend - 1.5Lakh/M) Interview Experience (Round 1) – Tree DP

Anonymous User
389
Aug 07, 2026

You are given a weighted binary tree, where each edge has a positive integer weight. Your task is to remove a set of edges such that every leaf node becomes disconnected from the root. Removing an edge incurs a cost equal to its weight. Find the minimum total cost required to disconnect all leaf nodes from the root.

Follow-up
The interviewer then generalized the problem:

How would you solve the same problem if the tree were an N-ary tree instead of a binary tree?

Comments (2)