FastPrepMerge Row Trees by Key Path

Merge Row Trees by Key Path

Hudson River Trading logoHudson River Trading● MediumINTERNOA

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 left and a node of right merge, the new node has their shared key and the value of the right node.
  • The new node's children are the left node's children in order, followed by the right node'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 the left child and is not repeated among the right children.
  • 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 from right, which is 11.
  • The root's children are 2, 3 from left and then 3, 4 from right. Key 3 is on both sides, so the two nodes merge and stay where left had key 3. Key 4 is only in right, so it comes last. The order is 2, 3, 4.
  • Key 3 merges with value 31. Its children are 5 from left and then 6, 5 from right. Key 5 merges with value 51 and stays first. Key 6 comes 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 4 and merge with value 5.
  • The root's children are 9 from left and then 4, 9 from right. Key 9 merges and stays first. Key 4 is only in right at this level, so its whole subtree, 4 (value 6) and its child 9 (value 8), comes after.
  • The merged key 9 takes value 7. Its children are 4 (value 3) from left and 2 (value 9) from right. 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 <= 1000
  • 2 <= left[i].length, right[i].length <= 1001
  • Every number in every row is a non-negative integer.
  • In each row, 0 <= key <= 10^4 and 0 <= value <= 10^9.
  • Each child index is a row index of the same tree, from 0 to the number of its rows minus 1.
  • 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

Similar questions at other companies

Hudson River Trading interview experiences

All Hudson River Trading interview questionsSee Hudson River Trading hiring insights
Saved
class Solution {
    public int[][] mergeTrees(int[][] left, int[][] right) {
        // Write your code here.
    }
}
Checking account…