Build and Validate a Binary Tree from Parent-Child Pairs

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.