FastPrepValidate a Tree From Its Parent Array
Problem · Array

Validate a Tree From Its Parent Array

Learn this problem
● MediumGoogle logoGoogleINTERNPHONE SCREEN
See Google hiring insights

Problem statement

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 problems

drafts saved locally
public boolean isValidTree(int[] parent) {
  // write your code here
}
parent[-1,0,0,1,1]
expectedtrue
checking account