Problem statement

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/

Solution

First, let us parse our string: we split it with - and keep d is depth. We will kieep in vals pairs value, depth. Then we use stack to simulate our process:

  1. While depth of current node is not equal to the top of stack + 1, that it is not children, we remove it from stack.
  2. Create node.
  3. Increase number of visited children for topf of the stack by one.
  4. If we have only one visited children, attach it to the left, in the opposite case to the right.
  5. Add this new node to stack.

Complexity

It is O(n) for time and space, where n is the total length of s.

Code

class Solution:
    def recoverFromPreorder(self, S):
        vals, d, ind = [], 0, 1

        for elem in S.split("-"):
            if elem != "": vals.append([int(elem), d])
            d = 1 if elem != "" else d + 1

        root = TreeNode(vals[0][0])
        stack = [[root, 0, 0]]  #node, level, visited_children

        for ind in range(1, len(vals)):
            while vals[ind][1] != stack[-1][1] + 1: stack.pop()

            Node = TreeNode(vals[ind][0])
            stack[-1][2] += 1
            if stack[-1][2] == 1:
                stack[-1][0].left = Node
            else:
                stack[-1][0].right = Node

            stack.append([Node, vals[ind][1], 0])
            
        return root