Terminal Nodes: Count and Return All Leaf Nodes Satisfying a Value Condition

Question

## Problem

Given the root of a binary tree, return all terminal (leaf) nodes whose value satisfies a given predicate. Additionally, after collecting them, prune the tree so that no remaining leaf node fails the predicate — repeat pruning until stable.

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

def terminal_nodes(root: TreeNode, predicate) -> tuple[list[int], TreeNode]:
    # Return (list of original leaf values passing predicate, pruned tree root)
    pass
```

**Example:**
```
Tree:      5
          / \
         3   8
        / \
       1   4
predicate = lambda v: v % 2 == 0
Leaves passing: [4, 8]
After pruning: root=5, right=8 (node 3 and 1 removed)
```

## Follow-ups

1. What is the time complexity of a single pruning pass? How many passes can be needed in the worst case?
2. How would you implement this iteratively without recursion?
3. Extend to an N-ary tree — what changes in your approach?
4. If the predicate is expensive (e.g., a network call), how do you minimize calls?

Terminal Nodes: Count and Return All Leaf Nodes Satisfying a Value Condition

Question Details

Full Details

Topics

More from Uber