## Problem Given the root of a binary tree, a node is "bad" if its value does not lie within the range `[min_val, max_val]` inherited from its ancestors (similar to BST validity). Remove all bad nodes and their subtrees. Return the modified root. ```python class TreeNode: def __init__(self, val=0, left=None, right=None): ... def remove_bad_nodes( root: TreeNode, min_val: int = float('-inf'), max_val: int = float('inf') ) -> TreeNode | None: pass ``` **Example:** ``` Tree: 5 / \ 1 8 / \ 0 3 Range enforced: left child must be parent Node 8 is bad if 8 > 5 is allowed, but 0 < 1 left of 5... walk through your definition. Output: cleaned tree with only valid-range nodes remaining. ``` ## Follow-ups 1. How does the valid range narrow as you traverse left vs. right? 2. What is the time complexity? Can you do this iteratively? 3. If a bad node has valid children, should the children be re-attached? Why or why not? 4. How would you extend this to an N-ary tree where each child has a specific position constraint?

Bad Nodes: Remove All Nodes in a Tree That Fail a Validity C

Question Details

Problem

Given the root of a binary tree, a node is "bad" if its value does not lie within the range [min_val, max_val] inherited from its ancestors (similar to BST validity). Remove all bad nodes and their subtrees.

Return the modified root.

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None): ...

def remove_bad_nodes(
    root: TreeNode,
    min_val: int = float('-inf'),
    max_val: int = float('inf')
) -> TreeNode | None:
    pass

Example:

Tree:     5
         / \
        1   8
       / \
      0   3
Range enforced: left child must be < parent, right child must be > parent
Node 8 is bad if 8 > 5 is allowed, but 0 < 1 left of 5... walk through your definition.

**Output**: cleaned tree with only valid-range nodes remaining.

Follow-ups

How does the valid range narrow as you traverse left vs. right?
What is the time complexity? Can you do this iteratively?
If a bad node has valid children, should the children be re-attached? Why or why not?
How would you extend this to an N-ary tree where each child has a specific position constraint?

Full Details

Problem

Given the root of a binary tree, a node is "bad" if its value does not lie within the range [min_val, max_val] inherited from its ancestors (similar to BST validity). Remove all bad nodes and their subtrees.

Return the modified root.

python
class TreeNode:
    def __init__(self, val=0, left=None, right=None): ...

def remove_bad_nodes(
    root: TreeNode,
    min_val: int = float('-inf'),
    max_val: int = float('inf')
) -> TreeNode | None:
    pass

Example:

Tree:     5
         / \
        1   8
       / \
      0   3
Range enforced: left child must be < parent, right child must be > parent
Node 8 is bad if 8 > 5 is allowed, but 0 < 1 left of 5... walk through your definition.

**Output**: cleaned tree with only valid-range nodes remaining.

Follow-ups

How does the valid range narrow as you traverse left vs. right?
What is the time complexity? Can you do this iteratively?
If a bad node has valid children, should the children be re-attached? Why or why not?
How would you extend this to an N-ary tree where each child has a specific position constraint?

Free preview. Unlock all Xai questions →

About This Question

This is a reported interview question from a xai interview during the onsite round.

It covers the following topics: Binary Tree, Coding, Onsite .

Topics

Binary Tree Coding Onsite

Bad Nodes: Remove All Nodes in a Tree That Fail a Validity Condition

Question Details

Problem

Full Details

Problem

About This Question

Topics

More Xai Interview Questions