Problem statement

A binary tree was walked in preorder (node, then its left subtree, then its right subtree). For every node the walk wrote D dashes, where D is the node's depth (the root has depth 0), immediately followed by the node's value. Everything was written into one string with no separators.

Whenever a node has exactly one child, that child is its left child.

Given the string traversal, rebuild the tree and return its root.

Example 1

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
Explanation: 1 is the root; 2 and 5 are at depth 1; 3, 4 hang under 2 and 6, 7 under 5.

Example 2

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]
Explanation: 3 and 6 each have one child, which is therefore on the left.

Example 3

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]
Explanation: After 90 at depth 3 the walk climbs back to depth 2 for 88, the second child of 401.

Constraints

• The number of nodes is in the range [1, 1000]
• 1 <= Node.val <= 10^9

Hints for Recover a Tree From Preorder Traversal

1. Hint 1

   Read the string as a sequence of (depth, value) pairs: count the dashes, then read the digits.

2. Hint 2

   In preorder, the parent of a node at depth D is the most recent node seen at depth D - 1.

3. Hint 3

   Keep a stack holding the current root-to-node path. Before attaching a node at depth D, pop until the stack has exactly D nodes; then it is the left child of the top if that slot is empty, otherwise the right child.

How to solve Recover a Tree From Preorder Traversal

Preorder visits a node right after its parent's earlier descendants, so the node's parent is always on the current root-to-node path, at depth one less. A stack holding that path, trimmed to the right depth before each node, rebuilds the tree in one left-to-right scan.

Approach

1. Scan the string. Count consecutive dashes to get the depth D, then parse the following digits as the value.
2. Pop the stack until its size equals D — what remains is the path from the root to the new node's parent.
3. If the stack is not empty, attach the new node to the top: as the left child if that is still empty, otherwise as the right child.
4. Push the new node.
5. When the string ends, the bottom of the stack is the root.

Why it works

In a preorder walk, once a node at depth D is written, every node written later at a depth greater than D belongs to its subtree until a node at depth D or less appears. So the deepest node at depth D - 1 written so far is the new node's parent, and the stack, trimmed to size D, has exactly that node on top. A parent receives its left child first, so filling the left slot before the right reproduces the tree — and a single child lands on the left, as promised.

Complexity

• Time — O(L), L the length of the string
• Space — O(h) for the stack

Pitfalls

• Values have several digits — read until the next dash, not a single character.
• Pop to size D, not D - 1: the stack's size is the depth of the next free level.
• Values reach 10^9, which still fits a 32-bit int; accumulate them as you read digits.

Reference solution

Python

from typing import Optional

def recoverFromPreorder(traversal: str) -> Optional[TreeNode]:
    stack = []
    i, n = 0, len(traversal)
    while i < n:
        depth = 0
        while traversal[i] == '-':
            depth += 1
            i += 1
        value = 0
        while i < n and traversal[i] != '-':
            value = value * 10 + ord(traversal[i]) - 48
            i += 1
        node = TreeNode(value)
        del stack[depth:]
        if stack:
            parent = stack[-1]
            if parent.left is None:
                parent.left = node
            else:
                parent.right = node
        stack.append(node)
    return stack[0]

Java

public static TreeNode recoverFromPreorder(String traversal) {
    List<TreeNode> stack = new ArrayList<>();
    int i = 0, n = traversal.length();
    while (i < n) {
        int depth = 0;
        while (traversal.charAt(i) == '-') { depth++; i++; }
        int value = 0;
        while (i < n && traversal.charAt(i) != '-') { value = value * 10 + (traversal.charAt(i) - '0'); i++; }
        TreeNode node = new TreeNode(value);
        while (stack.size() > depth) stack.remove(stack.size() - 1);
        if (!stack.isEmpty()) {
            TreeNode parent = stack.get(stack.size() - 1);
            if (parent.left == null) parent.left = node; else parent.right = node;
        }
        stack.add(node);
    }
    return stack.get(0);
}

C++

TreeNode* recoverFromPreorder(string traversal) {
    vector<TreeNode*> stack;
    size_t i = 0, n = traversal.size();
    while (i < n) {
        size_t depth = 0;
        while (traversal[i] == '-') { depth++; i++; }
        int value = 0;
        while (i < n && traversal[i] != '-') { value = value * 10 + (traversal[i] - '0'); i++; }
        TreeNode* node = new TreeNode(value);
        stack.resize(depth);
        if (!stack.empty()) {
            TreeNode* parent = stack.back();
            if (!parent->left) parent->left = node; else parent->right = node;
        }
        stack.push_back(node);
    }
    return stack[0];
}

JavaScript

var recoverFromPreorder = function(traversal) {
    var stack = [];
    var i = 0, n = traversal.length;
    while (i < n) {
        var depth = 0;
        while (traversal[i] === '-') { depth++; i++; }
        var value = 0;
        while (i < n && traversal[i] !== '-') { value = value * 10 + (traversal.charCodeAt(i) - 48); i++; }
        var node = new TreeNode(value);
        stack.length = depth;
        if (depth > 0) {
            var parent = stack[depth - 1];
            if (parent.left === null) parent.left = node; else parent.right = node;
        }
        stack.push(node);
    }
    return stack[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard