FastPrepMerge Hierarchical Trees by Name
Problems/Merge Hierarchical Trees by Name

Merge Hierarchical Trees by Name

Google logoGoogle● MediumFULLTIMEINTERNONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report defines name-based occurrence pairing, value precedence, and exact child-retention order. Parallel-array input and preorder-string output are specified for practice; the judged task matches at about 97%.

Two ordered rooted trees are encoded by parallel names, values, and parents arrays. Nodes are listed in preorder. The root is index 0 with parent -1; each later parent index is smaller than its child index. Sibling order is their order in the arrays.

Merge the two roots. A merged node takes its name from the first tree and its value from the second tree. For each pair of merged parents, children with the same name are paired in occurrence order and merged recursively.

  • Keep every child from the first tree in its original order.
  • Copy an unmatched first-tree child with its complete subtree unchanged.
  • After those children, append every unmatched second-tree child with its complete subtree in its original order.

Return the merged tree in preorder. Encode each node as depth:name:value, where the root depth is 0.

Function

mergeHierarchies(names1: String[], values1: int[], parents1: int[], names2: String[], values2: int[], parents2: int[]) → String[]

Examples

Example 1

names1 = ["root","a","x","a"]values1 = [1,2,3,4]parents1 = [-1,0,1,0]names2 = ["other","a","y","a","z","b"]values2 = [10,20,30,40,50,60]parents2 = [-1,0,1,0,3,0]return = ["0:root:10","1:a:20","2:x:3","2:y:30","1:a:40","2:z:50","1:b:60"]

The first and second a children pair by occurrence. Unmatched first-tree children remain before unmatched second-tree children, and the second-tree b child is appended last.

Example 2

names1 = ["r","left"]values1 = [1,2]parents1 = [-1,0]names2 = ["r2","right"]values2 = [9,8]parents2 = [-1,0]return = ["0:r:9","1:left:2","1:right:8"]

The root uses the first root's name and second root's value. Its differently named children remain in first-tree then second-tree order.

Constraints

  • 1 <= names1.length, names2.length <= 2000.
  • Within each tree, the three parallel arrays have equal lengths.
  • Nodes are listed in preorder; parents[0] == -1 and 0 <= parents[i] < i for i > 0.
  • Every name contains lowercase English letters, has length from 1 through 30, and contains no colon.
  • Node values fit in a signed 32-bit integer.
  • Tree depth is at most 500.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String[] mergeHierarchies(String[] names1, int[] values1, int[] parents1, String[] names2, int[] values2, int[] parents2) {
        // Write your code here.
    }
}
Checking account…