# 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[0]))]
        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[0][1])
        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][0] >= item[0]:
                stack.pop()
            node = TreeNode(item[1])
            if stack[-1][1].left:
                stack[-1][1].right = node
            else:
                stack[-1][1].left = node
            stack.append((item[0], 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

# Code (C++)

Approach 1:

Approach 2: