Get Components in Forest (for Virtual Interview)
Google● MediumOAProblem 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^5nodesis 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
edgesidentifies an existing parent-child edge, and no edge is repeated. - Return the component sizes in non-increasing order.