Build and Validate a Binary Tree from Parent-Child Pairs
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Build and Validate a Binary Tree from Parent-Child Pairs
You are given a single input string that is supposed to describe a binary tree as a sequence of parent-child pairs, for example:
```
(A,B) (B,C) (A,D)
```
Each pair has the form `(P,C)`, meaning node `P` is the parent of node `C`. Node values are single uppercase English letters `A`–`Z`. Your task is to validate the input and, if it describes a valid binary tree, print the tree's S-expression. If the input is invalid, print the highest-priority error code instead.
### Input format (strict)
A *well-formed* input string consists of one or more pairs, where:
- Each pair is exactly `(` + one uppercase letter + `,` + one uppercase letter + `)` — no spaces inside a pair.
- Consecutive pairs are separated by exactly one space.
- There is no leading or trailing whitespace, and no other characters appear anywhere.
The input may be **any** arbitrary string, so it must be checked carefully against this format. Any deviation from the format above (wrong characters, lowercase letters, multi-character node names, missing parentheses or commas, extra/missing spaces, empty string, etc.) is a format error.
### Errors
After format validation, check the described graph. Report exactly one error code — if several errors are present simultaneously, report the one with the highest priority. `E1` is the highest priority and `E5` is the lowest:
- **E1 — Invalid Input String**: the input string does not match the strict format described above.
- **E2 — Duplicate Pair**: the exact same pair `(P,C)` appears more than once.
- **E3 — Parent Has More than 2 Children**: some node appears as the parent in more than two (distinct) pairs.
- **E4 — Multiple Roots**: more than one node has no parent.
- **E5 — Cycle In The Tree**: the edges do not form a valid tree because some node can be reached in more than one way — there is a directed cycle (including a self-pair such as `(A,A)`), or some node has more than one parent.
If any error applies, output only its code, e.g.:
```
E3
```
### Output for valid input
If the input passes all checks, it describes a single binary tree. Print its S-expression, defined recursively as:
```
S(node) = "(" + node value + S(first child) + S(second child) + ")"
```
where a missing child contributes the empty string, and the children of each node are ordered so that the smaller letter (lexicographically) comes first. There are no spaces in the output.
### Examples
**Example 1**
```
Input: (A,B) (B,C) (A,D)
Output: (A(B(C))(D))
```
`A` is the root with children `B` and `D` (`B` printed first); `B` has one child `C`.
**Example 2**
```
Input: (A,B) (A,C) (B,D) (D,C)
Output: E5
```
`C` has two parents (`A` and `D`), so the structure is not a valid tree.
**Example 3**
```
Input: (A,B) (A,C) (B,D) (A,E)
Output: E3
```
`A` has three children.
**Example 4**
```
Input: (A,B) (b,C)
Output: E1
```
Lowercase `b` violates the input format.
**Example 5**
```
Input: (A,B) (A,B) (B,C)
Output: E2
```
The pair `(A,B)` appears twice.
### Constraints
- The input string length is at most $10^4$ characters.
- Node values are limited to the 26 uppercase letters, so a valid tree has at most 26 nodes.
- Your solution must return the error checks in strict priority order: `E1 > E2 > E3 > E4 > E5`.