Design HTML Element TreemediumDesign HTML Element Tree
Think about a small HTML document: a div may contain text, a ul, and several nested li elements. Text cannot have children, while an element can contain either text or more elements. Even so, every node must know how to render itself and describe its contribution to the whole tree.
This exercise focuses on that shared behavior. The starter code already provides MarkupTree, including ids, validation, and insertion. Your job is to implement only the three Composite participants:
MarkupNode, the common contract for every node in the document.TextLeaf, which represents a line of text.TagNode, which owns child nodes and handles nested rendering and aggregation.
The provided MarkupTree facade behaves as follows:
MarkupTree(String rootTag)creates a tree whose root is an empty element with that tag name. The root always has id0.int addElement(int parentId, String tag)adds an element under the node with that id and returns the new node's id. It returns-1when no node has that id, or when that node is a text node.int addText(int parentId, String text)adds a text node the same way and returns its id, or-1under the same two conditions.String render()returns the whole tree as markup.int textCount()returns how many text nodes the tree holds.int tagCount()returns how many elements the tree holds, counting the root.int depth()returns how many levels the tree has. A root on its own is1.
Ids are handed out in order starting at 1, and an add that returns -1 consumes no id.
The rendering rules are:
- A text node is its own text at the indent it was given.
- An element with children opens with
<tag>at its own indent, renders each child two spaces further in, and closes with</tag>back at its own indent. - An element with no children is written as
<tag></tag>on a single line.
The text carries no trailing newline.
The tests call MarkupTree, and the facade delegates rendering and aggregation to your node classes. Do not reimplement the facade.
Example 1:
Input:
Output:
Explanation: ul sits inside div and each li sits inside ul, so the two text lines end up six spaces in. Each closing tag returns to the indent of the tag that opened it, which is why </li> is four spaces in and </div> is at the margin.
Example 2:
Input:
Output:
Explanation: hr has no children, so it collapses onto one line. Deep sits three levels below the root, which makes depth 4, and tagCount counts section, hr, div and p.
Constraints
0 <= parentId <= 2001 <= tag.length <= 100 <= text.length <= 40- Tags and text contain letters, digits, spaces and colons only.
- At most
100calls in total are made across all methods.
Starter Code
Only the three Composite participants are unfinished. Implement the shared node contract, the text leaf, and the tag composite at the marked locations. MarkupTree is already implemented and should not be rewritten.
How the design is graded
needs 7/10 to pass- One contract for text and elements
Full marks when a text node and an element implement the same node interface, an element holds one list of that interface, and its recursive methods never test which concrete child type they received. Lose points heavily when text and elements are stored separately or children are stored as concrete leaf types.
- Recursion produces the nesting
Full marks when an element renders each child at two more spaces than its own indent and lets that child repeat the same rule, and when `textCount`, `tagCount` and `depth` are all built from the same call on every child. Lose points heavily when nesting beyond one level is missing, or when the counts only look at direct children.
- Leaf and element behavior
Full marks when the closing tag sits at the element's own indent, an empty element renders as `<tag></tag>` on one line, and a text leaf renders at the indent it receives while contributing one text node, zero tags and depth 1. Lose points for returning extra newlines or printing to stdout.
Passing every test is not enough on its own. A submission is accepted only when the design also clears the bar.
| Call | Returns |
|---|---|
| new MarkupTree("div") | null |
| addText(0, "My List:") | 1 |
| addElement(0, "ul") | 2 |
| addElement(2, "li") | 3 |
| addText(3, "Item 1") | 4 |
| addElement(2, "li") | 5 |
| addText(5, "Item 2") | 6 |
| render() | "<div>\n My List:\n <ul>\n <li>\n Item 1\n </li>\n <li>\n Item 2\n </li>\n </ul>\n</div>" |
| textCount() | 3 |
| tagCount() | 4 |
| depth() | 4 |
`ul` sits inside `div` and each `li` sits inside `ul`, so the two text lines end up six spaces in. Each closing tag returns to the indent of the tag that opened it, which is why `</li>` is four spaces in and `</div>` is at the margin.
Run checks these cases. Submit also runs a larger hidden set.