FastPrepDelete Nodes and Return Forest Roots
Problems/Delete Nodes and Return Forest Roots

Delete Nodes and Return Forest Roots

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionExamples

Problem statement

Source note: Google asked this in the first round of a new-grad onsite loop. It is the well-known Delete Nodes And Return Forest problem. The candidate named it only by its number, spelled with sound-alike characters. The same round also had a behavioral part.

The report gave no details on the variant. We chose the public problem's binary tree and limits. Instead of returning the trees themselves, the answer is their root values in increasing order. That fully pins down the forest, because each kept node stays under its kept parent.

Our version is about 85% the same as the reported question.

You are given the root of a binary tree in which every node has a different value, and an array toDelete.

Delete every node whose value appears in toDelete. Removing a node also removes the links to its parent and its children, so the remaining nodes split into a forest: a set of separate trees.

The problem statement continues
Pro

Examples

Example 1

root = [1,2,3,4,5,6,7]toDelete = [3,5]return = [1,6,7]
root
1245367
  • Deleting 3 cuts off its children 6 and 7, so each becomes the root of its own tree.
  • Deleting 5 leaves nothing behind, since 5 is a leaf.
  • Node 1 keeps 2 and 4. The roots are 1, 6 and 7.
02 · Example 2
FastPrep Pro
Reported in 1 Google interview this week

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
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week

More Google Onsite Interview questions

  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
  • Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
  • Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Russian Doll EnvelopesONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Top View of a Binary TreeInMobi · ONSITE INTERVIEWInMobi interview questions
  • Team Cost Under a ManagerRippling · PHONE SCREENRippling interview questions
  • N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
  • Page Referrer ReachabilityAmazon · ONSITE INTERVIEW
  • Merge N-Ary Trees by KeyLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
  • Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
  • Render an Org Chart and Find Skip-Level PairsSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
  • Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Bottom View of a Binary TreeOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
  • Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Google interview this week

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
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week