FastPrepValidate a Tree From Its Parent Array
Problems/Validate a Tree From Its Parent Array

Validate a Tree From Its Parent Array

Google logoGoogle● MediumINTERNNEW GRADPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report does not give input limits, the original function signature, or examples. Our version is about 97% the same as the reported question.

You are given a parent array parent describing a directed parent relationship over nodes numbered from 0 through parent.length - 1.

  • parent[i] = -1 means node i is a root.
  • Otherwise, parent[i] is the index of node i's parent.

Return true if the array describes exactly one valid rooted tree, and return false otherwise.

A valid rooted tree has exactly one root, contains no directed cycle, and makes every node reachable from that root.

Function

isValidTree(parent: int[]) → boolean

Examples

Example 1

parent = [-1,0,0,1,1]return = true

Node 0 is the unique root. Every other node is reachable from it, and no parent edge creates a cycle.

Example 2

parent = [-1,2,1]return = false

Nodes 1 and 2 form a directed cycle and are not reachable from the root.

Example 3

parent = [-1,-1,0]return = false

Nodes 0 and 1 are both roots, so the structure is not one rooted tree.

Constraints

  • 1 <= parent.length <= 2 * 10^5.
  • Every parent[i] is either -1 or an integer from 0 through parent.length - 1.

More Google Phone Screen questions

  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
  • Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
  • Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
  • Aggregate Machine TopologyOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
  • Deterministic Depth-First Graph TraversalWaymo · PHONE SCREENWaymo interview questions
  • Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
  • Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
  • All Nodes Distance K in a Binary TreeAmazon · PHONE SCREEN
  • Detonate Bombs with Chain ReactionsAirbnb · PHONE SCREENAirbnb interview questions
  • Report Island Areas in Discovery OrderSnap Inc. · PHONE SCREENSnap Inc. interview questions
  • Tree DiameterQualcomm · PHONE SCREENQualcomm interview questions

Interview reports that mention this question

  • Google New Grad R1 Valid Tree From Parent Array: 1 Experience

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
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public boolean isValidTree(int[] parent) {
      // write your code here
    }

}
Checking account…