1
class Solution:
2
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
3
        i = 0
4
        dummy_head = TreeNode()
5
        depth = 0
6
        while i < len(traversal):
7
            if traversal[i].isdigit():
8
                value, i = get_value(traversal, i)
9
                insert_node(dummy_head, depth, value)
10

11
            else:
12
                depth, i = get_depth(traversal, i)
13

14
        return dummy_head.left
15

16

17
# Returns the next value from the string traversal, and returns the position following the last digit of the current value.
18
def get_value(traversal, i):
19
    value = 0
20
    while i < len(traversal) and traversal[i].isdigit():
21
        value *= 10
22
        value += int(traversal[i])
23
        i += 1
24

25
    return value, i
26

27

28
# Insertes a node of the given `value` at the given `depth` of the subtree whose root is the given `root`.
29
def insert_node(root, depth, value):
30
    for _ in range(depth):
31
        if root.right:
32
            root = root.right
33
        else:
34
            root = root.left
35

36
    new_node = TreeNode(value)
37
    if root.left:
38
        root.right = new_node
39
    else:
40
        root.left = new_node
41

42

43
# Gets the next depth from the string traversal, and returns the position following the last dash of the current depth.
44
def get_depth(traversal, i):
45
    depth = 0
46
    while i < len(traversal) and traversal[i] == "-":
47
        depth += 1
48
        i += 1
49

50
    return depth, i