Merge Row Trees by Key Path
Updated
Problem statement
A tree is given as a list of rows, one row per node. The row [key, value, c1, c2, ...] describes a node with that key and value. The numbers after the first two are the row indices of the node's children, in order. Row indices start at 0. A node with no children has a row of just two numbers.
The rows can come in any order. The root is the one row that no other row lists as a child. A node can have any number of children, and the children of one node always have different keys. The same key can still appear in other parts of the tree.
You are given two trees, left and right. Merge them with these rules:
- If the two roots have different keys, the merged tree is empty.
- Otherwise the two roots merge. When a node of
leftand a node ofrightmerge, the new node has their shared key and the value of therightnode. - The new node's children are the
leftnode's children in order, followed by therightnode's children in order, with one exception. When a child key appears under both nodes, those two children merge into one child by these same rules. That child stays at the position of theleftchild and is not repeated among therightchildren. - A child that appears under only one of the two nodes is kept with its whole subtree, unchanged.
In other words, two nodes merge exactly when the keys on the path from the root down to them are the same in both trees.
Return the merged tree in pre-order: each node comes before its children, and the children are visited in order. Write each node as [key, value]. If the merged tree is empty, return an empty array.
A tree can be a single path of up to 1000 nodes, so a recursive solution must be able to go that deep.
Function
mergeTrees(left: int[][], right: int[][]) → int[][]Examples
Example 1
left = [[3,30,3],[1,10,2,0],[2,20],[5,50]]right = [[1,11,1,2],[3,31,3,4],[4,41],[6,61],[5,51]]return = [[1,11],[2,20],[3,31],[5,51],[6,61],[4,41]]No row of left lists row 1 as a child, so row 1 is its root. The left tree is key 1 (value 10) with children key 2 (value 20) and key 3 (value 30). Key 3 has one child, key 5 (value 50).
The root of right is row 0. The right tree is key 1 (value 11) with children key 3 (value 31) and key 4 (value 41). Key 3 has children key 6 (value 61) and key 5 (value 51).
- Both roots have key
1, so they merge. The merged root keeps the value fromright, which is11. - The root's children are
2, 3fromleftand then3, 4fromright. Key3is on both sides, so the two nodes merge and stay wherelefthad key3. Key4is only inright, so it comes last. The order is2, 3, 4. - Key
3merges with value31. Its children are5fromleftand then6, 5fromright. Key5merges with value51and stays first. Key6comes after it.
Reading the merged tree in pre-order gives keys 1, 2, 3, 5, 6, 4.
Example 2
left = [[7,1]]right = [[8,2,1],[7,3]]return = []The root of left has key 7. The root of right is row 0, with key 8. The roots have different keys, so the merge is empty and the answer is an empty array. It does not matter that right also has a node with key 7, because that node is not the root.
Example 3
left = [[9,2,2],[4,1,0],[4,3]]right = [[9,8],[2,9],[4,6,0],[9,7,1],[4,5,2,3]]return = [[4,5],[9,7],[4,3],[2,9],[4,6],[9,8]]The left tree is key 4 (value 1) → key 9 (value 2) → key 4 (value 3), a single path. Its root is row 1.
The root of right is row 4: key 4 (value 5) with children key 4 (value 6) and key 9 (value 7). The child with key 4 has one child, key 9 (value 8). The child with key 9 has one child, key 2 (value 9).
- The roots both have key
4and merge with value5. - The root's children are
9fromleftand then4, 9fromright. Key9merges and stays first. Key4is only inrightat this level, so its whole subtree,4(value6) and its child9(value8), comes after. - The merged key
9takes value7. Its children are4(value3) fromleftand2(value9) fromright. They have different keys, so both are kept, left first.
The key-4 node under 9 in left and the key-4 node under the root in right do not merge. They have the same key but sit at different places in their trees.
Pre-order gives [4,5], [9,7], [4,3], [2,9], [4,6], [9,8].
Constraints
1 <= left.length, right.length <= 10002 <= left[i].length, right[i].length <= 1001- Every number in every row is a non-negative integer.
- In each row,
0 <= key <= 10^4and0 <= value <= 10^9. - Each child index is a row index of the same tree, from
0to the number of its rows minus1. - In each tree, exactly one row is listed by no other row as a child. Every other row is listed as a child exactly once, and every row can be reached from the root.
- The children of one node have different keys.
More Hudson River Trading Online Assessment questions
- Count Palindrome Addition ChoicesOA · Seen Nov 2026
- Count Multiples of Three with Two SevensOA · Seen Oct 2026
- Recursively Expanded Shell Command CountsOA · Seen Oct 2026
- Rotate Matrix Regions Around the DiagonalsOA · Seen Oct 2026
- Maximum Diamond SumOA · Seen Oct 2026
- Smallest Most-Lit Street PositionOA · Seen Oct 2026
- Rearrange String by Alternating EndsOA · Seen Sep 2026
- Most Items Within Budget from a Start IndexOA · Seen Sep 2026
- Count Sawtooth SubarraysOA · Seen Aug 2026
- Backtick Identifier ConverterOA · Seen Jun 2026
Similar questions at other companies
- Build and Render an Organization Role TreeStripe · OAStripe interview questions
- Get Most Hydrated TeamAirtable · OAAirtable interview questions
- Palindromic Paths to the RootRippling · OARippling interview questions
- Validate BST Node DescriptionsAirbnb · OAAirbnb interview questions
- Render an Org Chart and Find Skip-Level PairsSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Merge N-Ary Trees by KeyLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions