FastPrep
Problem · Tree

Construct Binary Tree S-Expression

Learn this problem
● MediumOptiverOA

Problem statement

You are given a string containing parent-child pairs for a binary tree. Each pair is formatted like (A,B), meaning A is the parent of B.

If the pairs form a valid binary tree, return its S-expression. A node is rendered as (value leftSubtree rightSubtree), omitting empty children. When a node has two children, render them in lexicographic order by node label.

If the input is invalid, return the highest-priority error code:

  1. E1: Invalid input string.
  2. E2: Duplicate pair.
  3. E3: A parent has more than two children.
  4. E4: Multiple roots.
  5. E5: Cycle in the tree.

Function

validateBinaryTree(pairs: String) → String

Complete validateBinaryTree.

  • String pairs: a space-separated list of parent-child pairs

Returns

String: either an S-expression or an error code.

Examples

Example 1

pairs = "(A,B) (B,C) (A,D)"return = "(A(B(C))(D))"

The pairs form a valid tree rooted at A.

Example 2

pairs = "(A,B) (A,B)"return = "E2"

The pair (A,B) appears twice.

Constraints

  • 1 <= pairs.length <= 10^5
  • Node labels are uppercase English letters in the visible examples; hidden tests may use the same token format.

More Optiver problems

drafts saved locally
public String validateBinaryTree(String pairs) {
  // write your code here
}
pairs"(A,B) (B,C) (A,D)"
expected"(A(B(C))(D))"
checking account