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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Recover a Tree From Preorder Traversal

Number: 1093

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, Meta, Amazon

Problem Description

Given a string representing the preorder traversal of a binary tree where each node is represented by D dashes (indicating its depth) followed by the node's value, reconstruct the binary tree. The left child is always visited before the right child, and if a node has only one child, it is guaranteed to be the left child.

Key Insights

  • Use the number of dashes to determine the depth of the current node.
  • Leverage a stack to maintain the path of nodes from the root to the current node.
  • When a node with a smaller depth is encountered, pop nodes from the stack until the correct parent is found.
  • Each new node is attached as the left or right child based on whether the left child already exists.

Space and Time Complexity

Time Complexity: O(N) where N is the length of the traversal string (or number of nodes), since each character/node is processed once. Space Complexity: O(N) for the stack holding the path from the root to the deepest node.

Solution

To solve the problem, we iterate through the input string while counting consecutive dashes to identify the node depth and then read the integer value that follows. A stack is used to keep track of nodes corresponding to their depths. For every new node:

  1. Count the number of consecutive dashes to deduce its depth.
  2. Parse the integer for the node's value.
  3. If the current stack length is greater than the current depth, pop from the stack until its length equals the current depth.
  4. Attach the new node as a left child if the parent does not have one; otherwise, attach it as a right child.
  5. Push the new node onto the stack. This ensures that the tree is correctly rebuilt following the given preorder traversal.

Code Solutions

# 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) -> TreeNode:
        # Initialize stack to maintain nodes from root to current node
        stack = []
        index = 0
        n = len(traversal)
        
        # Process the traversal string
        while index < n:
            # Count dashes to determine the depth of the node
            depth = 0
            while index < n and traversal[index] == '-':
                depth += 1
                index += 1
            
            # Read the numeric value for the node
            value = 0
            while index < n and traversal[index].isdigit():
                value = value * 10 + int(traversal[index])
                index += 1
            
            # Create a new tree node with the parsed value
            node = TreeNode(value)
            
            # If stack length is greater than depth, pop until it matches the depth
            while len(stack) > depth:
                stack.pop()
            
            # If the stack is not empty, set the new node as left or right child
            if stack:
                parent = stack[-1]
                if not parent.left:
                    parent.left = node
                else:
                    parent.right = node

            # Push the new node onto the stack
            stack.append(node)
        
        # The bottom element of the stack is the root of the tree
        # Since we always bottom the stack first, return the root if exists
        return stack[0] if stack else None
← Back to All Questions