Checking a Tree Record With Hash Marks

Medium

A binary tree is written down as a string like this: walk it in preorder (node, left subtree, right subtree), write each node's value as a number and each empty subtree as #, and separate the entries with commas. For example, a tree whose root 1 has a childless left child 3 and no right child is written as "1,3,#,#,#". You are given a string record. Return True if it can be such a record of some binary tree, and False otherwise. The format is guaranteed to be well formed: every entry between commas is an integer or #, and there are never two commas in a row. You do not need to rebuild the tree itself.

Example 1

record="4,7,#,#,2,#,#" → True

Root 4 with children 7 and 2, both of which have empty subtrees.

Example 2

record="4,#" → False

Node 4 has only its left subtree recorded; the right one is missing.

Example 3

record="#,5,#,#" → False

The first # is already the whole (empty) tree, so anything after it is extra.

Constraints

1 ≤ len(record) ≤ 10⁴
record consists of integers from 0 to 100 and # characters, separated by commas

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Tree String Binary Tree

Similar problems

Tree From Bracket Notation Medium Tree Into a Right Chain Medium Preorder of a Search Tree Medium Tree in Compact Brackets Medium Peak-Split Tree Medium

Input

record="4,7,#,#,2,#,#"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 146 tests on the server, hidden ones included.