Check Whether a Template Occurs in Leaf Text of a Binary Tree

Given a binary tree whose leaves store characters (including possible spaces) and whose internal nodes store no text, visit leaves from left to right and concatenate their characters into a string S. Given a string template, determine whether it is a contiguous substring of S. Return true or false, and analyze the time and space complexity. For stdin/stdout, the tree is represented as a level-order array: * denotes an internal node; a single character denotes a leaf; # denotes a null node; _ denotes a space character in a leaf; every non-null node is either a leaf or has exactly two children. Input n tree[0] tree[1] ... tree[n-1] template Output true or false Constraints 1 <= n <= 2 * 10^5 Let L be the total number of leaf characters. 0 <= len(template) <= L Avoid materializing the full concatenated string S in extra linear space. Example Input 7 * * * a b c d bc Output true