Katkat
Back

Filter Matching Subtrees from an N-Ary Tree

WaymoFrontend Engineer · Onsite
MediumFrontend EngineerOnsiteCoding & Algorithms

Last updated

This problem tests tree traversal techniques, string matching, and the ability to handle iterative tree processing to avoid stack overflow in deep structures.

Problem Statement

Given an N-ary tree where each node has a value (a string) and a list of children, implement a function that prunes the tree. You are provided with a target substring forbidden. If any node's value contains the forbidden string, that node and its entire descendant subtree must be removed from the tree.

After pruning, return the remaining tree structure. If the root node itself contains the forbidden string, return null.

Constraints

  • The tree can be very deep (up to 100,000 levels), so you must avoid simple recursive approaches that hit stack depth limits.
  • Node values are strings of length 1 to 100.
  • Maintain the original relative order of remaining children.

Example

Input: Root: "data_A" Children: ["info_B", "data_C"] forbidden: "data"

Output: "info_B" (The root and "data_C" are removed)

Implementation

Provide your solution in Python using the following structure:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def prune_tree(root, forbidden):
    # Return the root of the modified tree
    pass

Hints

Hint 1

To handle deep trees, use an iterative traversal (like a stack-based post-order or level-order traversal) rather than relying on the call stack.

Hint 2

Perform a post-order traversal because the decision to remove a node depends on whether its children contain the forbidden string.

Hint 3

When processing a node, check if the value contains the forbidden string; if it does, discard the node entirely; otherwise, filter its children list based on the pruning results.

Follow-up questions

  • How would you handle the requirement to re-index nodes in a preorder traversal after the pruning is complete?
  • If this tree were stored in a flat array (e.g., [value, parent_index]), how would the pruning logic change?
  • What are the time and space complexity trade-offs of your iterative approach compared to a recursive one?