Merge N-ary Trees by Node Key

You are given the roots of two N‑ary trees, root1 and root2. Every node in these trees stores: an integer key (used to match nodes across the two trees), an integer val, and a list of child nodes (the children are stored in an array or list). Inside any node’s children list all keys are unique. The two input trees always have the same root key. Merge the two trees into a single N‑ary tree according to the rules below. The process must create a new tree without modifying the…