In a role-playing game, character abilities are organized into a binary talent tree: every skill node carries an integer skill ID and has up to two branches — a primary (left) branch and a secondary (right) branch, either of which may be absent. You are given a fully unlocked reference talent tree (the "main tree") and a smaller candidate tree (the "pattern tree"). Determine whether the pattern tree is a branch of the main tree: whether there exists some node of the main tree such that the branch rooted at that node has exactly the same shape as the pattern tree, with every corresponding pair of nodes carrying the same skill ID, all the way down to matching leaves and matching missing children.
Line 1: the main tree, serialized in level order (breadth-first) as space-separated tokens, where each token is either an integer skill ID or the literal null marking a missing child. The first token is the root. Whenever a token represents a real node, the next two tokens that appear in the stream are that node's left child and right child respectively (each either an integer or null); a node is treated as having no children once the stream simply runs out of tokens. The main tree always has at least one node.
Line 2: the pattern tree, serialized the same way. The pattern tree always has at least one node.
Print YES if the pattern tree matches a branch of the main tree exactly as described, otherwise print NO.
Example 1
Input
10 20 30 40 50 20 40 50
Expected
YES
Explanation
The main tree has root 10 with left child 20 and right child 30; node 20 has left child 40 and right child 50 (both leaves). The pattern tree is exactly root 20 with left child 40 and right child 50 — this matches the branch rooted at node 20 in the main tree exactly, so the answer is YES.
Example 2
Input
10 20 30 40 50 20 50 40
Expected
NO
Explanation
The pattern tree requires a node with left child 50 and right child 40, but the only node with skill ID 20 in the main tree has left child 40 and right child 50 (the opposite arrangement). No node in the main tree has this exact branch shape, so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →