1028. Recover a Tree From Preorder Traversal

HardView on LeetCode

Tree Depth-First Search String Binary Tree

Time: O(n)

Space: O(n)

Intuition

Parse (depth, value) pairs from string. Stack indexed by depth. Each node attaches to parent at depth-1.

Algorithm

1Parse: count dashes for depth, parse digits for value.
2stack[0..n]: stack[depth] = current node at that depth.
3Attach new node as left or right child of stack[depth-1]. Update stack[depth].

Common Pitfalls

•Leftmost child first. Parent is always at depth-1.

1028.cs

// Approach: Single-pass with a depth counter; track current index i; at each position count leading dashes to determine depth, then recursively build left/right subtrees.
// Time: O(n) Space: O(n)

public class TreeNode

    public TreeNode RecoverFromPreorder(string traversal)
    {
        return RecoverFromPreorder(traversal, 0);
    }

    private TreeNode RecoverFromPreorder(string traversal, int depth)
    {
        int nDashes = 0;
        while (i + nDashes < traversal.Length && traversal[i + nDashes] == '-')
            nDashes++;

        if (nDashes != depth)
            return null;

        i += depth;
        int start = i;
        while (i < traversal.Length && char.IsDigit(traversal[i]))
            i++;

        return new TreeNode(int.Parse(traversal.Substring(start, i - start)),
                            RecoverFromPreorder(traversal, depth + 1),
                            RecoverFromPreorder(traversal, depth + 1));
    }
}

Was this solution helpful?