We run a preorder depth first search on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.  (If the depth of a node is D, the depth of its immediate child is D+1.  The depth of the root node is 0.)
If a node has only one child, that child is guaranteed to be the left child.
Given the output S of this traversal, recover the tree and return its root.
 
Example 1:

Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]


Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]


 

Example 3:

Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]


 
Note:

The number of nodes in the original tree is between 1 and 1000.
Each node will have a value between 1 and 10^9.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        

Solutions:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import re

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        itera = re.finditer(r'(-*)(\\d+)', S)
        
        root = TreeNode(int(next(itera).group(2)))
        
        tofill = [root]
        
        for m in itera:
            k = len(m.group(1))
            if k == len(tofill):
                node = TreeNode(int(m.group(2)))
                tofill[-1].left = node
                tofill.append(node)
            else:
                node = TreeNode(int(m.group(2)))
                tofill[k-1].right = node
                tofill[k:] = [node]
        
        return root

class Solution:
    ''' Transform the input into following format:
        [ ... ,(num, num_level), ...]
        example: \"1-2--3--4-5\" -> [(1,0), (2,1), (3,2), (4,2), (5,1)]
    '''
    def __transform(self, S):
        split = S.split('-')
        index = 1
        res = [(split[0], 0)]
        while index < len(split):
            level = 0
            if split[index] == '':
                while split[index] == '':
                    level +=1
                    index +=1
            num = int(split[index])
            res.append((num, level+1))
            index += 1
        return res
    def recoverFromPreorder(self, S: str) -> TreeNode:
        L = {}
        trans_input = self.__transform(S)
        L[0] = TreeNode(trans_input[0][0], None, None)
        for num,level in trans_input[1:]:
            L[level] = TreeNode(num, None, None)
\t\t\t# Check if left of last level is mapped, ow map to right of last level.
            if not L[level-1].left:
                L[level-1].left = L[level]
            else:
                L[level-1].right = L[level]
        return L[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S: 
            return None
        if len(S) == 1: 
            return TreeNode(int(S))
        
        def split_str(S): 
            S += '-'
            ls = []
            start = 0
            for i in range(1, len(S)):
                if (S[i] == '-') & (S[i - 1] != '-'): 
                    ls.append(S[start: i])
                    start = i
            return ls
        
        ls_nodes = split_str(S)
        
        def build_tree(ls): 
            if not ls: 
                return None
            root = TreeNode(int(ls[0]))
            if len(ls) == 1: 
                return root
            
            lft = [ls[1][1:]]
            rgt = []
            flag = 0
            for i in range(2, len(ls)):
                if ls[i][1] != \"-\": 
                    flag = 1
                    rgt.append(ls[i][1:])
                else: 
                    if flag == 0: 
                        lft.append(ls[i][1:])
                    else: 
                        rgt.append(ls[i][1:])
                        
            root.left = build_tree(lft)
            root.right = build_tree(rgt)
            
            return root
        
        return build_tree(ls_nodes)
                    
        

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        ptr = 0
        def traverse(level: int) -> TreeNode:
            nonlocal ptr
            nextLevel = 0
            while ptr < len(S) and S[ptr] == '-':
                nextLevel += 1
                ptr += 1
                
            if level == nextLevel: 
                val = ''
                while ptr < len(S) and S[ptr] != '-':
                    val += S[ptr]
                    ptr += 1
                node = TreeNode(int(val))
                node.left = traverse(level+1)
                node.right = traverse(level+1)
                return node
            else:
                ptr -= nextLevel
                return None

        return traverse(0)


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def dfs(s, idx, depth):
            if idx==len(s):
                return None, len(s)
            cnt = 0
            while s[cnt+idx]=='-':
                cnt += 1
            
            if cnt!=depth:
                return None, idx
            
            idx += cnt
            i = 0
            while idx+i<len(s) and s[idx+i].isdigit():
                i += 1
            root = TreeNode(int(s[idx:idx+i]))
            idx += i
            root.left, li = dfs(s, idx, depth+1)
            root.right, ri = dfs(s, li, depth+1)
            return root, ri
        
        return dfs(S, 0, 0)[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def helper(depth):
            if depth != self.expected_depth:
                return None
            if self.i == len(S):
                return None
            n = 0
            while self.i < len(S) and S[self.i] != \"-\":
                n = n * 10 + int(S[self.i])
                self.i += 1
            self.expected_depth = 0
            while self.i < len(S) and S[self.i] == \"-\":
                self.expected_depth += 1
                self.i += 1
            node = TreeNode(n)
            node.left = helper(depth + 1)
            node.right = helper(depth + 1)
            return node
        
        self.i = 0
        self.expected_depth = 0
        return helper(0)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, s: str) -> TreeNode:
        self.index = 0
        def dfs(depth):
            if self.index == len(s):
                return
            for i in range(depth):
                if s[self.index+i] != '-':
                    return
            self.index += depth
            curr = 0
            while self.index < len(s) and s[self.index].isdigit():
                curr = curr * 10 + int(s[self.index])
                self.index += 1
            node = TreeNode(curr)
            node.left = dfs(depth+1)
            node.right = dfs(depth+1)
            return node
        return dfs(0)
    


from typing import Tuple

class TreeNode:
\tdef __init__(self, val, left=None, right=None):
\t\tself.val = val
\t\tself.left = left
\t\tself.right = right

class Solution:

\tdef _tokenize(self, s) -> Tuple[str, int]:
\t\tout = []
\t\tcur = \"num\"

\t\tfor c in s:

\t\t\tif c == \"-\":
\t\t\t\tnew = \"dash\"
\t\t\telse:
\t\t\t\tnew = \"num\"

\t\t\tif cur == new:
\t\t\t\tout.append(c)
\t\t\telse:
\t\t\t\tyield cur, \"\".join(out)
\t\t\t\tout = [c]
\t\t\t\tcur = new

\t\tyield cur, \"\".join(out)

\tdef tokenize(self, s):
\t\tfor type, token in self._tokenize(s):
\t\t\tif type == \"num\":
\t\t\t\tyield type, int(token)
\t\t\telse:
\t\t\t\tyield type, len(token)

\tdef recoverFromPreorder(self, S: str) -> TreeNode:

\t\tit = self.tokenize(S)
\t\t_, val = next(it)

\t\tm = {0: TreeNode(val)}
\t\tlevel = 0

\t\tfor type, value in it:
\t\t\tif type == \"dash\":
\t\t\t\tlevel = value
\t\t\t\tcontinue

\t\t\tn = TreeNode(value)
\t\t\tm[level] = n

\t\t\tif m[level - 1].left is None:
\t\t\t\tm[level - 1].left = n
\t\t\telse:
\t\t\t\tm[level - 1].right = n

\t\treturn m[0]


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def parsePath(self, s):
        depth = 0
        path = [0]
        for x in s:
            if x != \"-\" and depth > 0:
                path.append(depth)
                depth = 0
            elif x == \"-\":
                depth += 1
        return path
    
    def recoverFromPreorder(self, S: str) -> TreeNode:
        vals = [int(n) for n in filter(lambda x: x != \"\", S.split(\"-\"))]
        if len(vals) == 1:
            return TreeNode(vals[0])
        path = self.parsePath(S)
        stack = deque()
        
        print(path, vals)
        
        depth = i = 0
        root = node = None
        while i < len(path):
            if not root:
                root = TreeNode(vals[i])
                node = root
                i += 1
            
            if depth < path[i]:
                stack.append(node)
                if not node.left:
                    node.left = TreeNode(vals[i])
                    node = node.left
                else:
                    node.right = TreeNode(vals[i])
                    node = node.right
                depth += 1
                i += 1
            else:
                node = stack.pop()
                depth -= 1
            
        return root
        

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def method1():
            stack, i = [], 0
            while i < len(S):
                level, val = 0, \"\"
                while i < len(S) and S[i] == '-':
                    level+= 1
                    i+= 1
                    
                while i < len(S) and S[i] != '-':
                    val += S[i]
                    i += 1
                    
                while len(stack) > level:
                    stack.pop()
            
                node = TreeNode(val)
                if stack and stack[-1].left is None:
                    stack[-1].left = node
                elif stack:
                    stack[-1].right = node
                stack.append(node)
            return stack[0]
        
        return method1()

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
'''
Input: \"1-2--3--4-5--6--7\" 
i = 6, c=2, num=4, level = 1
j = 
'''
def getNext(s, i):
    c = 0

    while(i<len(s) and s[i]=='-'):
        i+=1
        c+=1
    num = []
    if i==len(s):
        return -1, -1, -1
    while(i<len(s) and s[i]!='-'):
        num.append(s[i])
        i+=1

    return c, int(''.join(num)), i

c, num, i = 0, 0, 0
def solve(s, level):
    
    nonlocal c,num,i
    c,num,j = getNext(s,i)
    
    if c==-1 or c<level:
        return None
    node = TreeNode(num)
    i = j
    node.left = solve(s,level+1)
    node.right = solve(s,level+1)
    
    return node   


class Solution:
    
    def recoverFromPreorder(self, S: str) -> TreeNode:
        nonlocal c,num,i
        c, num, i = 0, 0, 0
        return solve(S, 0)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S):
        stack, i = [], 0
        while i < len(S):
            level, val = 0, ''
            while i < len(S) and S[i] == '-':
                level, i = level + 1, i + 1
            while i < len(S) and S[i] != '-':
                val, i = val + S[i], i + 1
            while len(stack) > level:
                stack.pop()
            node = TreeNode(val)
            if stack and stack[-1].left is None:
                stack[-1].left = node
            elif stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import re

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        vals = [(len(s[1]), int(s[2])) for s in re.findall(\"((-*)(\\d+))\", S)][::-1]

        def dfs(level):
            if not vals or level != vals[-1][0]:
                return None

            node = TreeNode(vals.pop()[1])
            node.left = dfs(level + 1)
            node.right = dfs(level + 1)
            return node

        return dfs(0)
        

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S:
            return None
        self.idx = 0
        return self.recoverTree(S, 0)
    
    def recoverTree(self, s, depth):
        d = self.getDepth(s)
        if d != depth:
            self.idx -= d
            return 
        root = TreeNode(self.getVal(s))
        root.left = self.recoverTree(s, depth + 1)
        root.right = self.recoverTree(s, depth + 1)
        return root
        
    def getDepth(self, s):
        d = 0
        while self.idx < len(s) and s[self.idx] == '-':
            d += 1
            self.idx += 1
        return d
    
    def getVal(self, s):
        num = 0
        while self.idx < len(s) and s[self.idx].isdigit():
            num = num * 10 + int(s[self.idx])
            self.idx += 1
        return num
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import re
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        level_nodes = []
        c = 0
        print()
        for a in re.split(\"(\\d+)\", S):
            if a == '':
                continue
            elif '-' in a:
                c = len(a)
            else:
                level_nodes.append((c, a))
                c = 0

        def build_tree(arr, l, r, h, root):
            # root = arr[l]
            # assert root[0] == h,  f\"next level_nodes should be {h}\"

            kids = []
            for i in range(l, r+1):
                if arr[i][0] == h:
                    kids.append(i)
                if len(kids) == 2:
                    break
            # print(h, l, r, kids)
            if len(kids) == 0:
                return None
            elif len(kids) == 1:
                left = TreeNode(arr[kids[0]][1])
                root.left = left
                return build_tree(arr, kids[0]+1, r, h+1, left)
            else:
                left = TreeNode(arr[kids[0]][1])
                root.left = left
                build_tree(arr, kids[0]+1, kids[1]-1, h+1, left)
                right = TreeNode(arr[kids[1]][1])
                root.right = right
                return build_tree(arr, kids[1]+1, r, h+1, right)
            
        if len(level_nodes) == 0:
            return None        
        # print(level_nodes)
        root = TreeNode(level_nodes[0][1])
        build_tree(level_nodes, 1, len(level_nodes)-1, 1, root)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def _recoverFromPreorder(s):
            if not s:
                return

            root = TreeNode(s.pop())
            depth = 0
            while s:
                if s[-1] == '-':
                    s.pop()
                    depth += 1
                else:
                    break
            
            
            var = 0
            index = -1
            for i in range(len(s)-1, -1, -1):
                if s[i] != '-':
                    if var == depth:
                        index = i
                        break
                    var = 0
                else:
                    var += 1
                    
            if index == -1:
                root.left = _recoverFromPreorder(s)
            else:
                root.right = _recoverFromPreorder(s[:index+1])
                root.left = _recoverFromPreorder(s[index+depth+1:])
            
            return root
        
        arr = list(S)
        arr_1 = []
        
        x = ''
        while arr:
            s = arr.pop()
            if s == '-':
                if x:
                    arr_1.append(x)
                arr_1.append(s)
                x = ''
            else:
                x = s + x
                
        if x:
            arr_1.append(x)
            
        return _recoverFromPreorder(arr_1)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def _recoverFromPreorder(s):
            print (''.join(s))
            if not s:
                return

            root = TreeNode(s.pop())
            depth = 0
            while s:
                if s[-1] == '-':
                    s.pop()
                    depth += 1
                else:
                    break
            
            
            var = 0
            index = -1
            for i in range(len(s)-1, -1, -1):
                if s[i] != '-':
                    if var == depth:
                        index = i
                        break
                    var = 0
                else:
                    var += 1
                    
            if index == -1:
                root.left = _recoverFromPreorder(s)
            else:
                root.right = _recoverFromPreorder(s[:index+1])
                root.left = _recoverFromPreorder(s[index+depth+1:])
            
            return root
        
        arr = list(S)
        arr_1 = []
        
        x = ''
        while arr:
            s = arr.pop()
            if s == '-':
                if x:
                    arr_1.append(x)
                arr_1.append(s)
                x = ''
            else:
                x = s + x
                
        if x:
            arr_1.append(x)
            
        return _recoverFromPreorder(arr_1)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        stack = []
        i = 0
        level=0
        while i < len(S):
            level = 0
            val=''
            while i < len(S) and S[i] == '-':
                level+=1
                i+=1
            while i < len(S) and S[i] != '-':
                val += S[i]
                i+=1
            while len(stack)>level:
                stack.pop()
            node = TreeNode(val)
            if stack and stack[-1].left is None:
                stack[-1].left = node
            elif stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        dashes = 0
        stk = []
        i = 0
        while i < len(S):
            s = S[i]
            if s.isnumeric():
                c = s
                while i+1 < len(S) and S[i+1].isnumeric():
                    c += S[i+1]
                    i += 1
                while stk and dashes != stk[-1][1] + 1:
                    stk.pop()
                
                node = TreeNode(int(c))
                if stk and stk[-1][0].left:
                    stk[-1][0].right = node
                elif stk: stk[-1][0].left = node
                stk.append((node, dashes))
                dashes = 0
            
            else:
                dashes += 1
            
            i += 1
                
        return stk[0][0]
        
#         dashes = 0
#         node_depths = collections.defaultdict(list)
        
#         #root = TreeNode(int(S[0])))
#         expected_dashes = 1
        
#         for s in S:
#             if s.isnumeric():
#                 node_depths[dashes].append(int(s))
#                 dashes = 0
            
#             else:
#                 dashes += 1
        
#         stk = [TreeNode(int(S[0]))]
#         del node_depths[0]
#         for depth in sorted(node_depths):
#             for child in node_depths[depth]:
#                 if depth == 
            
        
        
        
        
        
#         traversal = [d for depth in sorted(node_depths) for d in node_depths[depth]]
#         print(traversal)
#         return traversal
    
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        return self.helper(S, 0)
        
    def helper(self, S, level):
        if not S:
            return None
        val = self.get(S)
        node = TreeNode(val)
        idx1, idx2 = self.find(S, level)
        if idx1:
            node.left = self.helper(S[idx1:idx2], level+1)
        if idx2:
            node.right = self.helper(S[idx2:], level+1)
        return node
    
    def find(self, S, level):
        idx1 = idx2 = None
        count = 0
        for i, ch in enumerate(S):
            if ch != '-':
                if count == level + 1:
                    if not idx1:
                        idx1 = i
                    else:
                        idx2 = i
                        return idx1, idx2
                count = 0
            else:
                count += 1
        return idx1, idx2
    
    def get(self, S):
        val = ''
        for ch in S:
            if ch == '-':
                break
            val += ch
        return val

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S: return None
        
        # \"1-2--3--4-5--6--7\"
        
        que = deque()
        root = TreeNode(int(S[0]))
        index = 0
        while index<len(S):
            depth = 0
            val = []
            while index<len(S) and S[index] == \"-\":
                depth += 1
                index += 1
            while index<len(S) and S[index].isnumeric():
                val.append(S[index])
                index += 1
            val = int(\"\".join(val))
            que.append((val, depth))
            
        
        def helper(depth=None):
            if not que: return None
            
            if depth is not None:
                if que[0][1] == depth or que[0][1]<depth: return None
            
            val, d = que.popleft()
            
            root = TreeNode(val)
            root.left = helper(d)
            root.right = helper(d)
            return root
        
        return helper()

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if S == '':
            return
        root = TreeNode(S.split('-')[0])
        stack = [(root,0)]
        nodes = []
        i = len(root.val)
        depth = 0
        val = []
        started = False
        while i < len(S):
            if S[i] == '-':
                if started:
                    nodes.append((TreeNode(''.join(val)),depth))
                    depth = 0
                    val = []
                    started = False
                depth += 1
            else:
                started = True
                val.append(S[i])
            i += 1
        nodes.append((TreeNode(''.join(val)),depth))
        print(nodes)
        for node in nodes:
            while len(stack) > 0 and node[1] <= stack[-1][1]:
                stack.pop()
            if len(stack) > 0:
                parent = stack[-1][0]
                if parent.left is None:
                    parent.left = node[0]
                else:
                    parent.right = node[0]
            stack.append(node)
        return root


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def transform(self, string):
        s = string.split('-')
        i = 1
        res = [(s[0], 0)]
        while i < len(s):
            l = 1
            if s[i] == '':
                while s[i] == '':
                    i += 1
                    l += 1
            res.append((int(s[i]), l))
            i += 1
        return res

    def recoverFromPreorder(self, S: str) -> TreeNode:
        L = {}
        trans = self.transform(S)
        L[0] = (TreeNode(trans[0][0]))
        for val, lvl in trans[1:]:
            L[lvl] = TreeNode(val)
            
            if L[lvl - 1].left:
                L[lvl - 1].right = L[lvl]
            else:
                L[lvl - 1].left = L[lvl]
        return L[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        leftChild = None
        rightChild = None
        if str.isnumeric(S):
            rootVal = S
        else:
            rootVal, S = S.split(\"-\", 1)
            S = \"-\" + S
            depths = re.split('\\d+', S)
            depths.pop()
            nodes = list(filter(None, re.split('-', S)))
            adjustedDepths = [d[1:] for d in depths]

            leftS = ''
            rightIdx = len(adjustedDepths)
            if '' in adjustedDepths[1:]:
                rightIdx = adjustedDepths[1:].index('') + 1
                rightS = ''
                for i in range(rightIdx, len(adjustedDepths)):
                    rightS = rightS + adjustedDepths[i] + nodes[i]
                rightChild=self.recoverFromPreorder(rightS)

            for i in range(rightIdx):
                leftS = leftS + adjustedDepths[i] + nodes[i]
            leftChild=self.recoverFromPreorder(leftS)
                

        return TreeNode(val=rootVal, left=leftChild, right=rightChild)
            
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S:
            return None
        if '-' not in S:
            return TreeNode(int(S))
        dashes,ind,n = 0,1, len(S)
        while ind<n and S[ind]>='0' and S[ind]<='9':
            ind+=1
        root = TreeNode(S[:ind])
        while ind<n and S[ind]=='-':
            ind+=1
            dashes+=1
        left_ind=ind
        
        
        ## start to find the right part
        dashes_right = 0
        while ind<n:
            dashes_right =0 
            while ind<n and S[ind]>='0' and S[ind]<='9':
                ind+=1
            while ind<n and S[ind]=='-':
                dashes_right+=1
                ind+=1
            if dashes_right==dashes:
                break
        if dashes_right==dashes:
            root.left = self.recoverFromPreorder(S[left_ind:ind-dashes_right])
            root.right = self.recoverFromPreorder(S[ind:])
        else:
            root.left = self.recoverFromPreorder(S[left_ind:])
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def dfs(s, level):
    if not s:
        return
    if len(s) == 1:
        return TreeNode(int(s[0]))
    ss = []
    nex = []
    c = 0
    l = 0
    for i in range(1, len(s)):
        if s[i] != \"-\":
            if len(ss) == level+1:
                nex.append(s[l:i-level-1])
                l = i
                c += 1
                if c == 2:
                    nex.append(s[i:])
                    break
            ss.clear()
        else:
            ss.append(\"-\")
    if c != 2:
        nex.append(s[l:])
        
    root = TreeNode(int(nex[0]))
    nex = nex[1:]
    if nex:
        root.left = dfs(nex[0], level+1)
        nex = nex[1:]
    if nex:
        root.right = dfs(nex[0], level+1)
        nex = nex[1:]
    return root


class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        return dfs(S, 0)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        ptr = 0
        def traverse(level: int) -> TreeNode:
            nonlocal ptr
            nextLevel = 0
            while ptr < len(S) and S[ptr] == '-':
                nextLevel += 1
                ptr += 1
                
            if level == nextLevel: 
                val = ''
                while ptr < len(S) and S[ptr] != '-':
                    val += S[ptr]
                    ptr += 1
                node = TreeNode(int(val))
                node.left = traverse(level+1)
                node.right = traverse(level+1)
                return node
            else:
                ptr -= nextLevel
                return None

        return traverse(0)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        #if the next node's num dashes increases , add as a child
        #also check next 
        
        #number of dashes tell you to move up/down
        
        #what does the order tell you?
        
        #there should only be 1 working node at each depth
        #keep a list of those
        #count the dashes, and then go to 1 above that
        
        
                
        nodes = []
        i = 0
        prev = \"\"
        for i in range(len(S)):
            if S[i] == \"-\" and prev == \"\":
                continue
            elif S[i] == \"-\":
                nodes.append(int(prev))
                prev = \"\"
            elif S[i] in list(\"0123456789\"):
                prev += S[i]
            else:
                assert False, f\"unrecognized char {S[i]}\"
        nodes.append(int(prev))
        
        depths = [0]
        prev = 0
        for i in range(len(S)):
            if S[i] in list(\"0123456789\") and prev == 0: #in the middle of a number, keep going
                continue
            if S[i] in list(\"0123456789\"): #ending a dash sequence, save the result
                depths.append(prev)
                prev = 0
            else: #middle of a dash sequence
                prev += 1
                
        assert len(nodes) == len(depths), \"should be same\"
        
        root = TreeNode(nodes[0])
        layers = [root] #keep track of the current node at each depth

        for i in range(1, len(nodes)):
            val = nodes[i]
            depth = depths[i]
            
            curr = TreeNode(val)
            assert depth <= len(layers)
            if depth == len(layers):
                layers.append(curr)
            else:
                layers[depth] = curr
            
            
            #go to the node 1 above
            parent = layers[depth-1]
            if parent.left == None:
                parent.left = curr
            else:
                assert parent.right == None, f\"{val}  {depth}   {parent}\"
                parent.right = curr
        return root
                            
            
            

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        def split(S, split_depth):
            split_index = -1
            i = len(S) - 1
            while i >= 0:
                temp_depth, size = i, 0
                while temp_depth < len(S) and S[temp_depth] == \"-\":
                    temp_depth -= 1
                    size += 1
                if size == split_depth:
                    split_index = temp_depth
                    break
                i = temp_depth
                i -= 1
            return split_index
        
        
        def process(S):
            node = None
            if len(S) != 0:
                depth = 0
                while depth < len(S) and S[depth] == \"-\":
                    depth += 1
                num = depth
                while num < len(S) and S[num].isdigit():
                    num += 1
                number = S[depth : num]
                node = TreeNode(int(number))
                S = S[num:]
                split_depth = depth + 1
                split_index = split(S, split_depth)
                if split_index != -1:
                    left, right = S[:split_index + 1], S[split_index + 1:]
                    node.left, node.right = process(left), process(right)
                else:
                    node.left, node.right = process(S), None                 
            return node
        return process(S)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        self.i = 0
        return self.construct_tree(S, 0)
        
    def construct_tree(self, S, level):
        if self.i == len(S):
            return None
        
        zero = ord('0')
        j = self.i
        node_lvl = 0
        while j < len(S) and S[j] == '-':
            node_lvl+=1
            j+=1

        val = 0
        while j < len(S) and S[j].isdigit():
            val = val*10 + (ord(S[j])-zero)
            j+=1
        
        if level != node_lvl:
            return None
        
        self.i = j
        return TreeNode(val, self.construct_tree(S, level+1), self.construct_tree(S, level+1))
        
        


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        
        if not S:
            return 
        
        ins = list(S)
        
        root = TreeNode(-1)
        current = None
        
        while ins:
            
            while ins and ins[0] == '-':
                
                # if right present
                if current.right:
                    current = current.right                
                # if left present
                elif current.left:
                    current = current.left
                
                ch = ins.pop(0)

            # node val can be multiple digits
            node_val = ''
            while ins and ins[0] != '-':
                ch = ins.pop(0)
                node_val += ch
                
            # if root None yet
            if not root.left:
                root.left = TreeNode(node_val)

            else:
                # if left not present
                if not current.left:
                    current.left = TreeNode(node_val)
                else:
                    current.right = TreeNode(node_val)

            # reset current
            current = root
            
        return root.left

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        
        def helper(current_depth, s):
            split_point1 = -1
            split_point2 = -1
            next_depth = current_depth + 1
            count = 0
            whole_count = 0
            for index, c in enumerate(s):
                if c == '-':
                    whole_count += 1
                    count += 1
                else:
                    if count == next_depth:
                        if split_point1 == -1:
                            split_point1 = index
                        else:
                            split_point2 = index
                    count = 0
            if whole_count == 0:
                return TreeNode(int(s))
            else:
                root = TreeNode(int(s[:split_point1 - next_depth]))

                if split_point2 != -1:
                    root.left = helper(next_depth, s[split_point1:split_point2 - next_depth])
                    root.right = helper(next_depth, s[split_point2:])
                else:
                    root.left = helper(next_depth, s[split_point1:])
                    root.right = None
            return root
        return helper(0, S)
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        idx = 0
        while idx < len(S) and S[idx] != '-':
            idx += 1
        root = TreeNode(int(S[:idx]))
        root_l = idx
        if len(S) == idx:
            return root
        d = 0
        while S[idx] == '-':
            d += 1
            idx += 1
        cnt = 0
        while idx < len(S):
            if S[idx] != '-':
                if cnt == d:
                    root.left = self.recoverFromPreorder(S[root_l+d:idx-d])
                    root.right = self.recoverFromPreorder(S[idx:])
                    break
                cnt = 0
            else:
                cnt += 1
            idx += 1
            if idx == len(S):
                root.left = self.recoverFromPreorder(S[root_l+d:])
        return root


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        try:
            self.values = [int(i) for i in S.split('-') if len(i)>0]
            self.S = S[S.index('-'):]
            root = TreeNode(self.values.pop(0))
        except:
            return TreeNode(int(S))
        

        def create_tree(root, depth):
            if len(self.S) == 0:
                return 
            elif '-' * depth == self.S[:depth]:
                if root.left == None:
                    num = self.values.pop(0)
                    digits = len(str(num))
                    tmp = TreeNode(num)
                    self.S = self.S[depth+digits:]
                    create_tree(tmp, depth+1)
                    root.left = tmp
                    
                if root.right == None and '-' * depth == self.S[:depth]:
                    num = self.values.pop(0)
                    digits = len(str(num))
                    tmp = TreeNode(num)
                    self.S = self.S[depth+digits:]
                    create_tree(tmp, depth+1)
                    root.right = tmp
                return root
            elif '-' * depth != self.S[:depth]:
                return
        
        # print(len(S))
        
        return create_tree(root, 1)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        #if the next node's num dashes increases , add as a child
        #also check next 
        
        #number of dashes tell you to move up/down
        
        #what does the order tell you?
        
        #there should only be 1 working node at each depth
        #keep a list of those
        #count the dashes, and then go to 1 above that
        
        
                
        nodes = []
        i = 0
        prev = \"\"
        for i in range(len(S)):
            if S[i] == \"-\" and prev == \"\":
                continue
            elif S[i] == \"-\":
                print(f\"appending prev {prev}\")
                nodes.append(int(prev))
                prev = \"\"
            elif S[i] in list(\"0123456789\"):
                prev += S[i]
            else:
                assert False, f\"unrecognized char {S[i]}\"
        nodes.append(int(prev))
        
        depths = [0]
        prev = 0
        for i in range(len(S)):
            if S[i] in list(\"0123456789\") and prev == 0: #in the middle of a number, keep going
                continue
            if S[i] in list(\"0123456789\"): #ending a dash sequence, save the result
                depths.append(prev)
                prev = 0
            else: #middle of a dash sequence
                prev += 1
                
        print(nodes, depths)
        assert len(nodes) == len(depths), \"should be same\"
        
        root = TreeNode(nodes[0])
        layers = [root] #keep track of the current node at each depth

        for i in range(1, len(nodes)):
            val = nodes[i]
            depth = depths[i]
            
            curr = TreeNode(val)
            assert depth <= len(layers)
            if depth == len(layers):
                layers.append(curr)
            else:
                layers[depth] = curr
            
            
            #go to the node 1 above
            parent = layers[depth-1]
            if parent.left == None:
                parent.left = curr
            else:
                assert parent.right == None, f\"{val}  {depth}   {parent}\"
                parent.right = curr
            print(curr)                
        return root
                            
            
            

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        first = S.find(\"-\")
        if \"-\"*len(S)==S:
            return None
        if first<0:
            if len(S)<1 :
                return None
            else:
                return TreeNode(int(S))
        
        root = TreeNode(int(S[:first]))
        stack = [(root, 0)]
        prev=0
        S = S[first:]
        while len(S)>0:
            curr_ = 0
            for idx, char in enumerate(S):
                if char==\"-\":
                    curr_+=1
                else:
                    break
            S = S[idx:]
            curr_num = \"\"
            for idx, char in enumerate(S):
                if char==\"-\":
                    break
                else:
                    curr_num+=char
            curr_num = TreeNode(int(curr_num))
            S = S[idx:]
            if prev < curr_: # then this is a child
                stack[-1][0].left = curr_num
                stack.append((curr_num, curr_))
            else:
                last = stack[-1]
                while stack and stack[-1][1]+1 >= curr_: # this is a right node or go one step up
                    # while checking where to attach the right node, we need to go one step above when we rech equality
                    # we need to go one step up,  if there is an equality hence on lhs there is the +1
                    last = stack.pop()
                last[0].right = curr_num
                stack.append((last[0].right, curr_))
            
            
            prev = curr_
            if len(S)==1:
                break
        
        return root
            

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def recoverFromPreorder(self, S: str) -> TreeNode:
      root_num = ''
      start = 0
      while S[start].isdigit():
        root_num += S[start]
        start += 1
        if start == len(S): break
      div = [(0, int(root_num))]
      depth_counter = 0
      while start < len(S):
        if S[start] == '-':
          depth_counter += 1
          start += 1
        else:
          num = ''
          while S[start].isdigit():
            num += S[start]
            start += 1
            if (start == len(S)): break
          div.append((depth_counter, int(num)))
          depth_counter = 0
      res = TreeNode(int(root_num))
      track = res
      dicts = {0:res}
      for i in range(1, len(div)):
        depth, val = div[i][0], div[i][1]
        roots = dicts[depth-1]
        if not roots.left:
          roots.left = TreeNode(val)
          dicts[depth] = roots.left
        else:
          roots.right = TreeNode(val)
          dicts[depth] = roots.right
      return res
      
      


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def recoverFromPreorder(self, S: str) -> TreeNode:
      root_num = ''
      start = 0
      while S[start].isdigit():
        root_num += S[start]
        start += 1
        if start == len(S): break
      div = [(0, int(root_num))]
      depth_counter = 0
      while start < len(S):
        if S[start] == '-':
          depth_counter += 1
          start += 1
        else:
          num = ''
          while S[start].isdigit():
            num += S[start]
            start += 1
            if (start == len(S)): break
          div.append((depth_counter, int(num)))
          depth_counter = 0
      res = TreeNode(int(root_num))
      track = res
      dicts = [res]
      for i in range(1, len(div)):
        depth, val = div[i][0], div[i][1]
        roots = dicts[depth-1]
        dicts = dicts[:depth]
        if not roots.left:
          roots.left = TreeNode(val)
          dicts.append(roots.left)
        else:
          roots.right = TreeNode(val)
          dicts.append(roots.right)
      return res
      
      


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        if not S: return None
        i=0
        d=0
        s=[]
        v=0
        while i<len(S) and S[i].isdigit():
            v=v*10+int(S[i])
            i+=1
        root=TreeNode(v)
        s.append((root, d))
        while i<len(S):
            if S[i].isdigit():
                v=0
                while i<len(S) and S[i].isdigit():
                    v=v*10+int(S[i])
                    i+=1
                nnode=TreeNode(v)
                if not s:
                    s.append((nnode, d))
                else:
                    node=s.pop()
                    while s and node[1]!=d-1:
                        node=s.pop()
                        
                    if not node[0].left:
                        node[0].left=nnode
                        s.append(node)
                        # s.append((nnode, d))
                    else:
                        node[0].right=nnode
                    s.append((nnode, d))
            else:
                d=0
                while i<len(S) and S[i]=='-':
                    d+=1
                    i+=1
        return root