#1028

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Recover a Tree From Preorder Traversal

Recover a binary tree from its preorder traversal string by tracking node depth and reconstructing child relationships efficiently.

string tree depth first search binary tree

Problem Statement

Given a string representing the preorder traversal of a binary tree, each node value is preceded by D dashes where D is its depth. The root node has depth 0, and for any node, its children appear immediately after it in the string, with their depth equal to the parent's depth plus one. If a node has only one child, it is always the left child.

Your task is to reconstruct the original binary tree from this traversal string. Return the tree as a standard binary tree structure or as an array representing level-order traversal with null placeholders for missing children. The traversal string contains only digits and dashes, and all node values are positive integers.

Examples

Example 1

Input: traversal = "1-2--3--4-5--6--7"

Output: [1,2,5,3,4,6,7]

Example details omitted.

Example 2

Input: traversal = "1-2--3---4-5--6---7"

Output: [1,2,5,3,null,6,null,4,null,7]

Example details omitted.

Example 3

Input: traversal = "1-401--349---90--88"

Output: [1,401,null,349,88,90]

Example details omitted.

Constraints

The number of nodes in the original tree is in the range [1, 1000].
1 <= Node.val <= 109

Solution Approach

Iterative Parsing with Depth Tracking

Scan the string character by character to extract node values and count leading dashes to determine depth. Maintain a stack of nodes representing the current path from the root to the latest node. Pop nodes from the stack until the top node's depth is one less than the new node's depth, then attach the new node as the left or right child accordingly and push it onto the stack.

Handle Single-Child Nodes

If a node has only one child, guarantee it is linked as the left child. The depth tracking ensures that when a new node appears at depth D+1, it is attached to the correct parent. This avoids misplacement errors where the child could be incorrectly assigned as right or skipped entirely.

Time and Space Optimization

The algorithm processes each character exactly once and each node is pushed and popped at most once from the stack, giving O(n) time complexity. Using a stack to track ancestors provides O(n) space usage, which is necessary to correctly manage node hierarchy and depth relations during reconstruction.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because we parse each character and node once. Space complexity is O(n) due to the stack holding up to all nodes along a path, which is essential to reconstruct the tree correctly.

What Interviewers Usually Probe

Ask if the candidate handles single-child nodes correctly as left children.
Check if the solution correctly counts dashes to determine node depth.
Watch for proper use of a stack or similar structure to maintain current ancestors.

Common Pitfalls or Variants

Common pitfalls

Miscounting dashes and attaching nodes to the wrong parent depth.
Assuming right children when a node has only one child, breaking tree structure.
Pushing all nodes onto the stack without popping ancestors, leading to incorrect hierarchy.

Follow-up variants

Recover tree from a preorder string with variable-length integers and missing children indicated explicitly.
Construct a tree from a preorder sequence where some nodes may be skipped or null explicitly.
Recover a binary tree while returning the result as a nested dictionary instead of array representation.

FAQ

What does 'Recover a Tree From Preorder Traversal' mean in practice?

It means reconstructing a binary tree from a string where node values are prefixed with dashes indicating their depth, restoring the original parent-child relationships.

Why is depth tracking necessary for this problem?

Depth tracking ensures each new node is attached to the correct parent, especially when handling single-child nodes, maintaining the proper binary tree hierarchy.

Can this be solved recursively instead of iteratively?

Yes, recursion can track depth naturally, but an iterative stack-based approach often reduces call stack overhead and aligns with preorder traversal parsing.

What is the time complexity of reconstructing the tree?

The reconstruction runs in O(n) time, processing each character and node once, while correctly managing the depth-to-parent relationships.

How are single-child nodes handled in this reconstruction?

Any node with only one child is guaranteed to have it as the left child, so the algorithm attaches it accordingly based on the depth sequence.

terminal

Solution

Solution 1

#### Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Stack<TreeNode> stack = new Stack<>();
        int i = 0;

        while (i < traversal.length()) {
            int depth = 0;
            while (i < traversal.length() && traversal.charAt(i) == '-') {
                depth++;
                i++;
            }

            int num = 0;
            while (i < traversal.length() && Character.isDigit(traversal.charAt(i))) {
                num = num * 10 + (traversal.charAt(i) - '0');
                i++;
            }

            // Create the new node
            TreeNode newNode = new TreeNode(num);

            while (stack.size() > depth) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                if (stack.peek().left == null) {
                    stack.peek().left = newNode;
                } else {
                    stack.peek().right = newNode;
                }
            }

            stack.push(newNode);
        }
        return stack.isEmpty() ? null : stack.get(0);
    }
}

Continue Practicing

#988 smallest string starting from leaf #606 construct string from binary tree #449 serialize and deserialize bst