A quality auditor inspects pairs of circuit boards. Each board is modeled as a binary tree: every node is a soldered component stamped with an integer code, and each component may branch to a left sub-board and a right sub-board through its two output pins. Two boards are considered wired identically only if they have exactly the same shape — every branch that exists on one board exists in the same left/right position on the other — and every pair of components in matching positions carries the same code. Given descriptions of board A and board B, determine whether they are wired identically.
Each board is described by a level-order token sequence built as follows: start a queue containing just the root's token. Repeatedly dequeue a token: if it is null, it contributes no further tokens (that branch simply ends); otherwise it is a component code, and it is followed in the sequence by its left child's token and then its right child's token (each again either an integer code or null), both of which get enqueued for further expansion only if they are not null. The sequence for a board is exactly the tokens produced this way, in order, with nothing extra appended. A board with no components at all is described by the single token null.
Line 1: the token sequence for board A, as space-separated tokens (each an integer or the literal null).
Line 2: the token sequence for board B, in the same format.
Print true if the two boards are wired identically (same shape and same codes at every matching position), or false otherwise.
Example 1
Input
1 2 3 1 2 3
Expected
true
Explanation
Both token sequences build the same shape: a root coded 1 with a left child coded 2 and a right child coded 3. Every position matches, so the boards are wired identically and the answer is true.
Example 2
Input
1 2 null 1 null 2
Expected
false
Explanation
Board A's sequence "1 2 null" builds a root coded 1 whose left child is coded 2 and whose right child is absent. Board B's sequence "1 null 2" builds a root coded 1 whose left child is absent and whose right child is coded 2. Both boards use the same two codes, but the component coded 2 sits on the left in board A and on the right in board B, so the shapes disagree and the answer is false.
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 →