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:

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.

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).

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