FastPrep
Problem · Tree

Get Components in Forest (for Virtual Interview)

Learn this problem
● MediumGoogleOA
See Google hiring insights

Problem statement

Given a binary tree with n nodes and an array edges where each element is of the form [from, to], representing an edge from from to to.

Remove all the edges in the edges array from the tree and return an array with the total node count in each connected component formed after removing all the edges from the tree.

Note: All the node values in the Binary Tree are unique.

Function

getComponentsInForest(Nodes: String[], Edges: int[][]) → int[]

Examples

Example 1

Nodes = ["1", "2", "3", "4", "5", "null", "null"]Edges = [[1, 2], [2, 4]]return = [2,2,1]
The output shows that there are 3 components formed after removing the edges from the binary tree, and number of nodes in those components are 2, 2 and 1 respectively.

Constraints

  • 1 ≤ nodes.length ≤ 10^5
  • nodes is the level-order representation of a non-empty binary tree; missing positions are represented by "null".
  • Every non-null node value is a unique integer encoded as a string.
  • Every pair in edges identifies an existing parent-child edge, and no edge is repeated.
  • Return the component sizes in non-increasing order.

More Google problems

drafts saved locally
public int[] getComponentsInForest(String[] nodes, int[][] edges) {
  // write your code here
}
Nodes["1", "2", "3", "4", "5", "null", "null"]
Edges[[1, 2], [2, 4]]
expected[2,2,1]
checking account