Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1093. Recover a Tree From Preorder Traversal

My accepted Python solution to LeetCode problem 1093, Recover a Tree From Preorder Traversal, running in 21ms.

  • Difficulty: Hard
  • Python
  • Runtime 21ms
  • Memory 18.1MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 21ms, memory 18.1MB, accepted 2026-01-02.

python
# 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, traversal: str) -> Optional[TreeNode]:
        stack = []
        i = 0
        
        while i < len(traversal):
            # Count depth (number of dashes)
            depth = 0
            while i < len(traversal) and traversal[i] == '-':
                depth += 1
                i += 1
            
            # Get the value
            val = 0
            while i < len(traversal) and traversal[i].isdigit():
                val = val * 10 + int(traversal[i])
                i += 1
            
            node = TreeNode(val)
            
            # Pop until we find the parent at depth-1
            while len(stack) > depth:
                stack.pop()
            
            # Attach to parent
            if stack:
                if stack[-1].left is None:
                    stack[-1].left = node
                else:
                    stack[-1].right = node
            
            stack.append(node)
        
        return stack[0]

Source