Implement menu parser and serializer

Menu parser and serializer

You are given a restaurant menu stored as plain text, where indentation represents a hierarchy of categories and items. Implement logic to convert between this text format and a tree data structure.

Text format

• The menu is a multi-line string; each non-empty line describes one menu item.
• Leading indentation (0 or more groups of two spaces) indicates nesting depth relative to top-level categories.
• After the indentation, fields on each line are separated by the | character: <type>|<id>|<name>|<price> where:
  • type is a string label such as CATEGORY , FOOD , or SIDE (you should not assume only these three types; treat it as an arbitrary string).
  • id is a unique identifier string for this item.
  • name is free text that does not contain the | character.
  • price is a decimal number (e.g., 5.99 ), or the literal - if the item does not have a price (e.g., a category).

Example input:

CATEGORY|c1|Burgers|-
  FOOD|f1|Classic Burger|5.99
    SIDE|s1|Fries|1.99
  FOOD|f2|Veggie Burger|6.49
CATEGORY|c2|Drinks|-
  FOOD|f3|Cola|1.50
  FOOD|f4|Water|1.00

This example represents a hierarchy like category > food > side, but in general the depth and item types can vary.

Tree structure

Define a data structure MenuItem (language-agnostic) with at least the following fields:

• type : string
• id : string
• name : string
• price : nullable/optional number (null if the text price is - )
• children : an ordered list/array of MenuItem representing nested items

Top-level menu items are those with zero indentation.

Tasks

1. Implement a function (e.g., parseMenu(text) ) that takes the menu text string and returns the corresponding tree: a list/array of top-level MenuItem nodes, each with properly populated children .
2. Implement a function (e.g., serializeMenu(items) ) that takes the tree (the list/array of top-level MenuItem nodes) and returns a canonical text representation in exactly the same format as described above.

The serializer must:

• Use exactly two spaces per level of indentation deeper than a parent.
• Use | as the field separator.
• Output - for items whose price is null/absent.
• Output a depth-first traversal, where all children of a node appear immediately after their parent, in the order stored in children .

You may assume the input text is always a valid, well-formed tree (no cycles, consistent indentation, and at least one top-level item).

Design your parsing and serialization logic to run in O(N) time and O(N) extra space, where N is the number of menu items (lines) in the input.