Filter a Tree by Substring and Render It Indented

intermediate

By FrontendAtlas Editorial · Updated Oct 14, 2026

Given an n-ary tree of { value, children } nodes and a needle string, drop every node whose value contains the needle together with its whole subtree, then render what remains as text: one line per node, depth-first in sibling order, indented two spaces per level. A public report of a senior frontend phone screen describes the same filter rendered as a UI tree; this practice version renders text so the tests can check order and indentation exactly. Concepts: tree, recursion, strings, immutability.

What you'll practice:

Pruning subtrees during a depth-first walk instead of filtering after the fact
Rendering tree depth as indentation without mutating the input
Defining the contract for a matching root, an empty needle and case sensitivity before coding

Expected behavior

Your renderFilteredTree() implementation should:

Return one line per surviving node, in depth-first order with siblings kept in their original order
Indent each line with two spaces per depth level and join lines with a newline, with no trailing newline
Drop a node and its entire subtree when node.value includes the needle (case-sensitive)
Return an empty string when the root itself matches
Prune nothing when the needle is an empty string
Leave the input tree unchanged

Arguments

root: { value: string; children?: TreeNode[] } — The root of an n-ary tree. children may be missing on leaves.
needle: string — The substring to prune by. A node whose value contains it disappears with its subtree.

Returns

string —

The surviving tree rendered as indented text, or an empty string when the root matches.

Solution idea

Interview answer: decide the contract first. A node is pruned when its value includes the needle, and pruning a node also removes its subtree, so the check belongs at the moment you visit a node, not in a post-processing filter. Walk depth-first, carry the depth with each node, and emit one line per surviving node with two spaces per level. Treat the root like any other node (a matching root yields an empty string) and treat an empty needle as "keep everything", because every string includes the empty string. Build a fresh array of lines so the input tree is never mutated.

Examples

// Prune the 'offline' branch and render the rest
const fleet = {
  value: 'fleet',
  children: [
    { value: 'depot-east', children: [{ value: 'van-12' }, { value: 'van-13-offline' }] },
    { value: 'depot-west-offline', children: [{ value: 'van-21' }] },
  ],
};
renderFilteredTree(fleet, 'offline');
// => 'fleet\
  depot-east\
    van-12'

// A matching root removes everything
renderFilteredTree(fleet, 'fleet'); // => ''

// An empty needle keeps the whole tree
renderFilteredTree({ value: 'a', children: [{ value: 'b' }] }, ''); // => 'a\
  b'

Public interview reports

These public, self-reported interview accounts informed this practice version. The exercise is modelled on reported rounds, not copied from them, and the reports are not verified official questions or endorsements.

PracHub: Waymo senior frontend engineer interview experience, May 2026 · PracHub, May 2026
One self-reported senior loop. It establishes that a tree-filter-and-render phone screen was asked once, rendered as UI in the report; this text-rendering version is a practice adaptation, not the exact wording.

Solution

Overview

Mental model: a pre-order traversal that skips a subtree whenever the gate fails, plus a depth counter that becomes indentation.

Approach 1: Recursive pre-order walk with a prune gate

Guard the root first: a missing root or a matching root returns an empty string. Then write a small recursive walk that pushes the current node's line, iterates its children in order, skips any child whose value includes the needle, and recurses with depth + 1. The depth is only used for indentation, so the walk never needs to copy nodes. Time is O(n) over the surviving nodes and memory is O(h) for the call stack plus the output lines.

export default function renderFilteredTree(root, needle) {
  if (!root) return '';
  if (needle && root.value.includes(needle)) return '';
  const lines = [];
  const walk = (node, depth) => {
    lines.push(`${'  '.repeat(depth)}${node.value}`);
    for (const child of node.children || []) {
      if (needle && child.value.includes(needle)) continue;
      walk(child, depth + 1);
    }
  };
  walk(root, 0);
  return lines.join('\n');
}

type TreeNode = { value: string; children?: TreeNode[] };

export default function renderFilteredTree(root: TreeNode | null | undefined, needle: string): string {
  if (!root) return '';
  if (needle && root.value.includes(needle)) return '';
  const lines: string[] = [];
  const walk = (node: TreeNode, depth: number): void => {
    lines.push(`${'  '.repeat(depth)}${node.value}`);
    for (const child of node.children || []) {
      if (needle && child.value.includes(needle)) continue;
      walk(child, depth + 1);
    }
  };
  walk(root, 0);
  return lines.join('\n');
}

Approach 2: Explicit stack (no recursion depth limit)

Replace the call stack with an explicit stack of { node, depth } frames. Pop a frame, emit its line, then push its children in reverse order so the first child is processed next and sibling order is preserved. Apply the same prune gate while pushing. This handles very deep trees without risking a stack overflow and makes the traversal order visible in code.

export default function renderFilteredTree(root, needle) {
  if (!root || (needle && root.value.includes(needle))) return '';
  const lines = [];
  const stack = [{ node: root, depth: 0 }];
  while (stack.length) {
    const { node, depth } = stack.pop();
    lines.push(`${'  '.repeat(depth)}${node.value}`);
    const children = node.children || [];
    for (let i = children.length - 1; i >= 0; i -= 1) {
      const child = children[i];
      if (needle && child.value.includes(needle)) continue;
      stack.push({ node: child, depth: depth + 1 });
    }
  }
  return lines.join('\n');
}

type TreeNode = { value: string; children?: TreeNode[] };

export default function renderFilteredTree(root: TreeNode | null | undefined, needle: string): string {
  if (!root || (needle && root.value.includes(needle))) return '';
  const lines: string[] = [];
  const stack: Array<{ node: TreeNode; depth: number }> = [{ node: root, depth: 0 }];
  while (stack.length) {
    const { node, depth } = stack.pop() as { node: TreeNode; depth: number };
    lines.push(`${'  '.repeat(depth)}${node.value}`);
    const children = node.children || [];
    for (let i = children.length - 1; i >= 0; i -= 1) {
      const child = children[i];
      if (needle && child.value.includes(needle)) continue;
      stack.push({ node: child, depth: depth + 1 });
    }
  }
  return lines.join('\n');
}

Notes & Pitfalls

Pitfalls

Filtering `children` after rendering keeps grandchildren of a pruned node alive; prune at visit time.
`''.includes('')` is true, so an unguarded empty needle prunes the entire tree.
Pushing children in forward order onto a stack reverses sibling order.

Edge cases

Root matches → `''`.
Leaf nodes may omit `children` entirely.
Needle present in a deep leaf only → that leaf disappears, its ancestors stay.
Case matters: `'Offline'` does not match `'offline'`.

Techniques

Pre-order depth-first traversal with a pruning gate.
Carrying depth alongside nodes to derive indentation.
Converting recursion to an explicit stack.

Common mistakes on this challenge

Prune matching subtrees before rendering
A node whose value contains the needle must disappear with its whole subtree; a matching root yields an empty string, and an empty needle prunes nothing.
- Check `value.includes(needle)` when you visit a node and skip its children when it matches.
- Return `''` when the root itself matches, and treat an empty needle as keep-everything.
- Keep the comparison case-sensitive and never mutate the input nodes.

Common interview follow-ups:

How would you render the result as nested DOM elements instead of text, and what changes in the traversal?
What if the needle should match case-insensitively or against several fields?
How would you keep an ancestor visible when only a descendant matches a positive filter instead of a prune?
How would you add collapse and expand state to the rendered tree without re-walking it on every toggle?

Resources

Guides

Frontend interview preparation guideGuide Frontend coding interview questions and prep guideBlueprint JavaScript Problems That Actually Show UpBlueprint Build Great UI in 60 MinutesBlueprint

Preparing for interviews? Use Frontend Coding Challenges first, then move into a concrete Study Plan before targeted Company Prep.

Open frontend interview questions Browse JavaScript interview questions Open Essential 60 Open Machine Coding Hub Open Frontend Coding Challenges Open System Design Open Interview Prep Guide Open System Design Blueprint Open Framework Prep Paths Open Study Plans Open JavaScript mastery study plan Open Company Prep Open JavaScript Framework Prep Guide

Built in public

The code behind FrontendAtlas lives on GitHub. A star helps other frontend engineers find it.

Star on GitHub