We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Recover a Tree From Preorder Traversal

Difficulty: Hard

Problem Description

Given a string representing the preorder traversal of a binary tree, where each node's depth is indicated by the number of dashes before its value, recover the tree and return its root.

Key Insights

  • The depth of the node is determined by the number of dashes preceding its value.
  • Each node is guaranteed to have its left child if it has one, meaning we don't need to account for right children in depth management.
  • We can utilize a stack to keep track of the current nodes at different depths and build the tree as we parse the input string.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We will use a stack to keep track of the nodes as we construct the tree. We will iterate through the input string, counting the dashes to determine the depth of each node. For each node value encountered, we will create a new node and link it to its parent based on the depth. The stack will help manage the current nodes and their relationships as we build the tree from the traversal string.

Code Solutions

def recoverFromPreorder(traversal: str):
    stack = []
    i = 0
    while i < len(traversal):
        level = 0
        # Count the number of dashes to determine the depth
        while i < len(traversal) and traversal[i] == '-':
            level += 1
            i += 1
        
        # Extract the node value
        val = 0
        while i < len(traversal) and traversal[i].isdigit():
            val = val * 10 + int(traversal[i])
            i += 1
        
        # Create a new node
        node = TreeNode(val)
        
        # If this is the first node, it becomes the root
        if level == 0:
            stack.append(node)
        else:
            # Attach to the last node at one less level
            while len(stack) > level:
                stack.pop()
            parent = stack[-1]
            if not parent.left:
                parent.left = node
            else:
                parent.right = node
        
        # Push the new node onto the stack
        stack.append(node)
    
    return stack[0]
← Back to All Questions