Search a Pattern Across the Leaf Text of a Binary Tree

Problem Statement

You are given the root of a binary tree where each leaf node contains a non-empty string val. Internal nodes do not contain text (their val is empty or None).

If you collect the strings from all leaf nodes in a left-to-right order and concatenate them into a single string T, determine whether a given non-empty pattern appears as a contiguous substring in T. The match may start in one leaf and end in another.

To ensure scalability for very large trees where T cannot fit into memory all at once, your solution should process the leaves as a stream with O(|pattern| + height) auxiliary space.

Function Interface

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

def search_leaf_pattern(root: Optional[TreeNode], pattern: str) -> bool:
    pass

Input & Output

• Input:
  • root: The root node of a binary tree.
  • pattern: A non-empty string to search for.
• Output: True if pattern is a contiguous substring of the concatenated leaf text, otherwise False.

Examples

Example 1

         ( )
        /   \
     ( )     ("xyz")
    /   \
("ab")  ("cd")

• Concatenated leaf text T = "abcdxyz"
• pattern = "bcdx"
• Output: True (the pattern spans across leaves "cd" and "xyz").

Example 2

     ( )
    /   \
("hello") ("world")

• Concatenated leaf text T = "helloworld"
• pattern = "word"
• Output: False

Constraints

• The number of nodes in the tree is between 1 and 10^5.
• Total characters across all leaves can be up to 10^7.
• 1 <= len(pattern) <= 10^5.
• All characters in leaf strings and pattern consist of lowercase English letters.
• Auxiliary space complexity should be O(|pattern| + H), where H is the height of the tree.