# Validate a Binary Tree Built from Directed Edges You are given a list of directed edges. Each edge is a pair `(parent, child)` of positive-integer node labels, meaning `parent` points to `child`. The set of nodes is exactly the set of labels that appear in at least one edge. Determine whether the edges form a single **valid binary tree**: - Exactly one root (a node with no parent). - Every non-root node has exactly one parent. - No node has more than two children. - There are no cycles, and every node is reachable from the root (equivalently, the edges form one connected tree, not a forest). If the edges do **not** form a valid binary tree, output the **first** error code that applies from the priority list below (check in this exact order and report only the highest-priority error): 1. `INVALID_INPUT` — some edge is a self-loop (`parent == child`), or the exact same `(parent, child)` edge appears more than once. 2. `TOO_MANY_CHILDREN` — some node appears as the parent in more than two edges. 3. `MULTIPLE_PARENTS` — some node appears as the child in more than one edge. 4. `CYCLE` — the edges contain a directed cycle. 5. `MULTIPLE_ROOTS` — more than one node has no parent (the edges form a forest of two or more trees). If the edges **do** form a valid binary tree, output its **in-order traversal serialization**: visit the left subtree, then the node, then the right subtree, and print the node labels separated by single spaces. ## Left/right child rule Edges are given in a fixed order. For any parent node: - The **first** edge listed with that node as parent attaches its **left** child. - The **second** edge listed with that node as parent attaches its **right** child. - A node with only one child edge has only a **left** child. ## Input - `edges`: a list of pairs `[parent, child]` of positive integers, in a fixed given order. ## Output Return a single string: - one of the five error codes above (exactly as spelled, uppercase) if the edges do not form a valid binary tree, or - the space-separated in-order traversal of the tree if they do. ## Examples **Example 1 — valid tree** ``` edges = [[1,2],[1,3],[2,4],[3,5]] ``` Node `1` has left child `2` and right child `3`; node `2` has left child `4`; node `3` has left child `5`. Output: `4 2 1 5 3` **Example 2 — cycle** ``` edges = [[1,2],[2,3],[3,1]] ``` Every node has exactly one parent and at most two children, but the edges form a directed cycle. Output: `CYCLE` **Example 3 — too many children** ``` edges = [[1,2],[1,3],[1,4]] ``` Node `1` has three children. Output: `TOO_MANY_CHILDREN` **Example 4 — multiple roots** ``` edges = [[1,2],[3,4]] ``` Nodes `1` and `3` both have no parent, so the edges form a forest. Output: `MULTIPLE_ROOTS` **Example 5 — duplicate edge** ``` edges = [[1,2],[1,2]] ``` The edge `(1,2)` appears twice. Output: `INVALID_INPUT` **Example 6 — multiple parents** ``` edges = [[1,2],[1,3],[2,4],[3,4]] ``` Node `4` has two parents (`2` and `3`). Output: `MULTIPLE_PARENTS` ## Constraints - `1 <= number of edges <= 10^4` - `1 <= node label <= 10^5` - Node labels within the tree are distinct identifiers; the same label never denotes two different nodes. - The error priority order must be respected: when several problems exist simultaneously, report only the highest-priority one.