Filter an N-ary Tree by Substring and Render It With Indentation in a UI

This phone screen for a senior frontend role has two connected parts. You are given an n-ary tree in which every node holds a string value and a list of children, for example: ```js const tree = { value: "root", children: [ { value: "sensors", children: [ { value: "lidar-front", children: [] }, { value: "camera-debug", children: [{ value: "frames", children: [] }] }, ] }, { value: "debug-tools", children: [{ value: "logger", children: [] }] }, { value: "planner", children: [] }, ], }; ``` (The node values here are illustrative.) ### Clarifying Questions - Is the substring match case-sensitive? - What should an empty filter string do: remove nothing, or remove everything? - May the original tree be modified, or must the function return a new tree? - If the root itself matches, what should be returned and displayed? - Is any framework expected for the UI, or is the choice yours? - How large can the tree get (depth and number of nodes)? ### Part 1 — Filter the tree Write a function that takes the tree and a substring and removes every node whose value contains the substring, **together with its entire subtree**, and returns the filtered tree. With the example tree and the substring `"debug"`, the nodes `camera-debug` (and its child `frames`) and `debug-tools` (and its child `logger`) disappear. ```hint When to decide A node's fate can be decided before looking at any of its children. ``` #### What This Part Should Cover - A correct recursive (or iterative) filter that drops matching nodes with their whole subtrees - Returning a new tree without mutating the input - The root-removed case and the empty-substring case - Time and space complexity in terms of nodes and string lengths ### Part 2 — Render the filtered tree Build a UI on top of Part 1: a text input and, below it, the filtered tree. Each node appears on its own line with indentation that reflects its depth, and the displayed tree must update correctly as the value in the input changes (including when the input is cleared). ```hint One source of truth Decide which piece of state the component owns and which things should be derived from it on every render. ``` #### Clarifying Questions for this Part - Should the tree update on every keystroke, or is a short delay acceptable for large trees? - Is a nested-list rendering acceptable, or must each line be a flat row with computed indentation? #### What This Part Should Cover - State design: the input value as state, the filtered tree derived from it - Recursive rendering with correct indentation and stable keys - Correct updates when the filter changes or is cleared, without losing the original data - Accessibility and performance considerations for large trees ### What a Strong Answer Covers - Clear handling of the ambiguous cases (case sensitivity, empty filter, removed root) before coding - Pure, testable filtering logic kept separate from the UI component - Rendering that stays correct when the same value appears in several places in the tree - Awareness of how the approach scales for deep or very large trees ### Follow-up Questions - Change the behavior so that matching nodes are **kept** and highlighted, along with the ancestors needed to reach them. What changes in Part 1? - The tree has 100,000 nodes and typing feels slow. What do you change? - Add expand and collapse for each node. Where does that state live, and what happens to it when the filter hides a node? - How would you test Part 2?