LeetCode 1028 - Recover a Tree From Preorder Traversal

The problem provides a string traversal representing a preorder depth-first traversal of a binary tree, where each node is represented by its value preceded by D dashes, with D being the depth of the node in the tree. The root node has depth 0 and is not preceded by any dash.

leetcodehardstringtreedepth-first-searchbinary-tree

LeetCode Problem 1028

Difficulty: 🔴 Hard
Topics: String, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem provides a string traversal representing a preorder depth-first traversal of a binary tree, where each node is represented by its value preceded by D dashes, with D being the depth of the node in the tree. The root node has depth 0 and is not preceded by any dash. If a node has only one child, it is guaranteed to be the left child. Our task is to reconstruct the original binary tree from this traversal and return the root.

The input string encodes the tree structure implicitly via dashes and values. For example, "1-2--3--4-5--6--7" represents a tree where 1 is the root, 2 is its left child, 5 is its right child, and so on, with deeper nodes indicated by increasing numbers of dashes. The constraints tell us there can be up to 1000 nodes, with node values up to 10^9. This ensures that parsing the values as integers is feasible and that we need an efficient algorithm to handle up to 1000 nodes without exceeding time limits.

Important edge cases include strings where nodes have only left children, strings with large integers, or nodes appearing consecutively at different depths without right children. The problem guarantees that the traversal string is valid according to the rules, so we do not need to handle malformed input.

Approaches

A brute-force approach would involve parsing the string, extracting each node's depth and value, then recursively inserting each node into the tree by comparing the current depth to the expected depth of children. This works correctly but may involve repeated scanning or backtracking to find the correct parent for each node, resulting in suboptimal time complexity.

The optimal approach leverages a stack to maintain the path from the root to the current node. While iterating through the traversal string, we determine each node's depth and value. If the depth of the current node is greater than the stack size, it is a left child of the node at the top of the stack. If the depth is smaller or equal, we pop nodes until the stack size equals the current depth, then attach the node as a right child. This ensures we always maintain the correct parent-child relationships in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Recursively insert each node by depth; may require scanning ancestors repeatedly
Optimal O(n) O(n) Use a stack to track ancestors; attach node as left/right child based on stack depth

Algorithm Walkthrough

  1. Initialize an empty stack that will hold nodes corresponding to the current path from the root to the current node.
  2. Iterate through the traversal string using an index pointer.
  3. For each node, first count the number of consecutive dashes to determine its depth.
  4. Then parse the integer value following the dashes.
  5. While the stack length is greater than the current depth, pop nodes from the stack. This ensures the top of the stack is always the parent of the new node.
  6. Create a new TreeNode with the parsed value.
  7. If the stack is not empty, check the parent at the top of the stack. If the parent does not have a left child, attach the new node as the left child; otherwise, attach it as the right child.
  8. Push the new node onto the stack.
  9. Repeat steps 3-8 until the entire string is parsed.
  10. The root of the tree is the first node pushed onto the stack.

Why it works: The stack invariant ensures that at any point, the stack contains the chain of nodes from the root to the current depth. By maintaining this property, we can attach new nodes correctly as left or right children without backtracking. Each node is processed exactly once, guaranteeing correctness and efficiency.

Python Solution

# 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
        n = len(traversal)
        while i < n:
            depth = 0
            while i < n and traversal[i] == '-':
                depth += 1
                i += 1
            val_start = i
            while i < n and traversal[i].isdigit():
                i += 1
            val = int(traversal[val_start:i])
            node = TreeNode(val)
            while len(stack) > depth:
                stack.pop()
            if stack:
                parent = stack[-1]
                if not parent.left:
                    parent.left = node
                else:
                    parent.right = node
            stack.append(node)
        return stack[0] if stack else None

In this implementation, we use a pointer i to iterate over the traversal string. We first count dashes to determine depth, then parse the number. By maintaining a stack of ancestors, we ensure correct parent-child relationships, popping nodes when the current depth indicates we need to backtrack. Each node is pushed onto the stack exactly once.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverFromPreorder(traversal string) *TreeNode {
    stack := []*TreeNode{}
    n := len(traversal)
    i := 0
    for i < n {
        depth := 0
        for i < n && traversal[i] == '-' {
            depth++
            i++
        }
        valStart := i
        for i < n && traversal[i] >= '0' && traversal[i] <= '9' {
            i++
        }
        val := 0
        for j := valStart; j < i; j++ {
            val = val*10 + int(traversal[j]-'0')
        }
        node := &TreeNode{Val: val}
        for len(stack) > depth {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            parent := stack[len(stack)-1]
            if parent.Left == nil {
                parent.Left = node
            } else {
                parent.Right = node
            }
        }
        stack = append(stack, node)
    }
    if len(stack) > 0 {
        return stack[0]
    }
    return nil
}

The Go version mirrors the Python logic. Instead of using int() for parsing, we manually convert characters to an integer. Slices are used for the stack, and nil checks replace Python's None. The algorithm maintains the same stack invariant and depth-based logic.

Worked Examples

Example 1: "1-2--3--4-5--6--7"

Step Depth Value Stack after operation Tree update
1 0 1 [1] Root node
2 1 2 [1,2] 2 is left child of 1
3 2 3 [1,2,3] 3 is left child of 2
4 2 4 [1,2,4] 4 is right child of 2
5 1 5 [1,5] 5 is right child of 1
6 2 6 [1,5,6] 6 is left child of 5
7 2 7 [1,5,7] 7 is right child of 5

Final tree matches [1,2,5,3,4,6,7].

Example 2: "1-401--349---90--88"

Step Depth Value Stack Tree
1 0 1 [1] Root node
2 1 401 [1,401] 401 left of 1
3 2 349 [1,401,349] 349 left of 401
4 3 90 [1,401,349,90] 90 left of 349
5 2 88 [1,401,88] 88 right of 401

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character in the string is processed exactly once to determine depth and value
Space O(n) Stack stores up to the height of the tree, which can be O(n) in worst-case skewed tree

The linear time complexity comes from scanning the string once, and space complexity comes from maintaining the stack, which at most contains one node per depth.

Test Cases

# Provided examples
assert Solution().recoverFromPreorder("1-2--3--4-5--6--7").val == 1  # balanced tree
assert Solution().recoverFromPreorder("1-2--3---4-5--6---7").val == 1  # uneven depth tree
assert Solution().recoverFromPreorder("1