Pin Down a Vague HTML Parser Prompt, Build the Element Tree, and Query It with DFS

You are asked to write an HTML parser. The prompt is deliberately vague: it does not define the input, the output, or which edge cases matter. Part of the exercise is turning it into a precise contract: ask for concrete examples early, then write down the input, the output and the edge cases before you start coding.

Once the contract is settled, implement a parser that captures how the elements of the document nest, and use the parsed structure to answer a question about the document.

Constraints and Clarifications

• Which question about the document the interviewer asked is not known. For practice, assume that once you ask, the interviewer wants this query: given a tag name, return the text content of every element with that tag, in document order, where an element's text content is all the text inside it, concatenated.
• Assume the input is one HTML string that fits in memory.

Clarifying Questions

• Can you show a concrete input and the exact output you expect for it?
• Is the input guaranteed to be well formed, with every opened element closed in the right order, or must the parser recover from missing or mismatched end tags?
• Which constructs can appear: attributes (quoted, unquoted or without a value), self-closing tags, void elements such as br and img that never have an end tag, comments, a doctype, character entities such as &?
• Are tag names case-insensitive, and should whitespace between tags be kept?
• Can script or style elements appear, whose content must not be parsed as markup?

Part 1 — Parse the input into a tree

Implement a parser that turns the input string into a tree: one node per element, holding its tag name, its attributes and its children in document order, with text stored in leaf nodes. Apply the edge-case policy you agreed on. A typical input:

<div class="card"><p>Hello <b>world</b></p><br><p>Fish &amp; chips</p></div>

What This Part Should Cover

• A node model for elements, attributes and text
• A single left-to-right pass that attaches every node to the correct parent
• The agreed handling of void elements, self-closing tags, comments, entities and malformed nesting
• Running time that is linear in the input length

Part 2 — Answer the query with a depth-first traversal

Using the tree from Part 1, implement the practice query. For the input above, the query for p returns ["Hello world", "Fish & chips"], and the query for b returns ["world"].

What This Part Should Cover

• A depth-first traversal that visits nodes in document order
• Collecting the text of a subtree, including text inside nested elements
• Recursion depth on deeply nested input, and the cost of a query when matching elements nest inside each other