Search a Pattern Across the Leaf Text of a Binary Tree
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Search a Pattern Across the Leaf Text of a Binary Tree
A rooted binary tree has nodes numbered from `0` through `n - 1`, with node `0` as the root. The arrays `left` and `right` store child indices; `-1` means that child is absent. A node is a leaf exactly when both child indices are `-1`. Each leaf contributes its string from `leaf_text`; values at internal nodes are ignored.
Visit leaves from left to right and concatenate their strings without separators. Return whether `pattern` occurs as a contiguous substring of that combined text. A match may begin in one leaf and end in another.
## Function Signature
```python
def contains_leaf_text(
left: list[int],
right: list[int],
leaf_text: list[str],
pattern: str,
) -> bool:
...
```
## Constraints
- `1 <= n <= 100_000`
- `len(left) == len(right) == len(leaf_text) == n`
- The child arrays describe one valid binary tree rooted at `0`.
- Leaf strings and `pattern` may contain arbitrary printable characters, including spaces.
- The total length of all leaf strings is at most `1_000_000`.
- `1 <= len(pattern) <= 100_000`
## Examples
```text
Input:
left = [1, -1, 3, -1, -1]
right = [2, -1, 4, -1, -1]
leaf_text = ["", "hel", "", "lo ", "world"]
pattern = "hello"
Output: true
```
```text
Input:
left = [1, -1, -1]
right = [2, -1, -1]
leaf_text = ["", "ab", "cd"]
pattern = "bc"
Output: true
```
Quick Answer: Search for a pattern across the left-to-right concatenation of binary-tree leaf strings, including matches that cross leaf boundaries. This algorithm problem combines tree traversal with scalable substring matching under large input limits.