Tree From a Dashed Preorder Record

Hard

A binary tree was walked in preorder (node, then left subtree, then right subtree) and written into a single string record: for each node there are as many dashes - as its depth, immediately followed by its value. The root has depth 0, and a child is one level deeper than its parent. If a node has only one child, that child is always the left one. Rebuild the tree from record and return its root.

Example 1

record="7-3--8-9" → [7, 3, 9, 8]

The root is 7 (no dashes). It has two children with one dash, 3 and 9; 3 has a single child 8, which is its left child.

Example 2

record="12-5--40---6" → [12, 5, None, 40, None, 6]

Each value is one level deeper than the previous, so the tree is a chain of left children.

Example 3

record="4" → [4]

Constraints

The tree has between 1 and 1000 nodes
1 ≤ node value ≤ 10⁹
record is a valid record of such a tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search String Binary Tree

Similar problems

Routes from Root to Leaves Easy Tree From Bracket Notation Medium Tree in Compact Brackets Medium Smallest Leaf-to-Root Word Medium Directions Through a Tree Medium

Input

record="7-3--8-9"

Expected

[7, 3, 9, 8]

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