A data-center operator runs a binary relay network: each relay forwards its traffic to at most two child relays, a left one and a right one. The monitoring system walks the network in a fixed order -- visit the current relay first, then walk its entire left branch, then walk its entire right branch -- and appends one entry per visit to a single audit log. Each entry is either an integer relay ID or the marker #, meaning "this branch position led to no relay at all" (a missing child, or the marker standing in for the empty network itself).
Given only the comma-separated audit log (with no spaces), determine whether it could have been produced by walking some valid binary relay network in the order described above -- without reconstructing the network.
A single line containing the comma-separated audit log: a sequence of tokens separated by commas, with no surrounding spaces. Each token is either the character # or the decimal representation of an integer relay ID (which may be negative).
Print true if the log could be a valid walk of some binary relay network, or false otherwise.
Example 1
Input
5,3,#,#,7,#,#
Expected
true
Explanation
Walking the log: relay 5 is the root; its left branch is relay 3, whose own left and right children are both missing (`#,#`); back at relay 5, its right branch is relay 7, whose children are also both missing (`#,#`). Every relay's two branch slots are accounted for and no tokens are left over, so the log is a valid walk and the answer is `true`.
Example 2
Input
5,3,#,#,#,7
Expected
false
Explanation
The first five tokens `5,3,#,#,#` already complete a valid two-relay network (root 5 with left child 3, and 3's two missing children) -- at that point every open branch slot has been filled. The trailing token `7` has no open slot left to fill, so it cannot belong to the walk. The log is not a valid walk 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 →