Convert a Multi-Children Tree Structure to a Binary Search Tree and Design Tests

You are given a tree-structured dataset where each node can have multiple children (an n-ary tree). Each node contains a comparable key (e.g., an integer). Convert/build these nodes into a Binary Search Tree (BST) such that an in-order traversal of the BST yields a non-decreasing sequence of keys. Requirements: Return the root of the resulting BST. If duplicate keys exist, define and implement a consistent rule (e.g., equal keys always go to the right subtree). You do not need to preserve the original parent/children relationships of the n-ary tree; you only need to include all node keys into the BST. (If you choose to preserve structure, state your strategy explicitly.) Also explain your testing approach: How you decompose the solution into testable components (e.g., traversal/collection, BST insertion/build, BST validation). What test scenarios you would cover for each component. You may define the input/output format, but it must be clearly documented in code. Assume a reasonable constraint such as total nodes N up to 1e5 for complexity discussion. Example Input 0 Output EMPTY