## # 1028. Recover a Tree From Preorder Traversal

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]
``````

### # Solution

Approach 1: iterative with a stack.

Approach 2: recursive -- consume the string along with the recursion.

### # Code (Python)

Approach 1:

``````    def recoverFromPreorder(self, string: str) -> TreeNode:
# iterative solution with a stack
if not string:
return None

# tokenize
splitted = string.split('-')
levels = [(0, int(splitted))]
count = 1
for item in splitted[1:]:
if not item:
count += 1
else:
levels.append((count, int(item)))
count = 1

# construct the tree
root = TreeNode(levels)
stack = [(0, root)] # could also store just the nodes, and check levels using len(stack) because we only store 1 node per level
for item in levels[1:]:
while stack[-1] >= item:
stack.pop()
node = TreeNode(item)
if stack[-1].left:
stack[-1].right = node
else:
stack[-1].left = node
stack.append((item, node))
return root
``````

Approach 2:

``````    def recoverFromPreorder(self, string):
# recursive solution
self.index = 0 # a global index that advances itself during the recursion
return self._construct(string, 0)

def _construct(self, string, expected_depth):
num_dashes = 0
while num_dashes + self.index < len(string) and string[self.index+num_dashes] == '-':
num_dashes += 1
# we get to a leaf or a node missing a subtree on the side
if num_dashes != expected_depth:
return None
digit_index = self.index + num_dashes
while digit_index < len(string) and string[digit_index] != '-':
digit_index += 1
root = TreeNode(int(string[self.index+num_dashes:digit_index]))
self.index = digit_index
root.left = self._construct(string, expected_depth + 1) # self.index advances itself after this operation
root.right = self._construct(string, expected_depth + 1)
return root
``````

Approach 1:

Approach 2: