Recover a Tree From Preorder Traversal - Practice Coding Problems

Recover a Tree From Preorder Traversal - Problem

We run a preorder depth-first search (DFS) on the root of a binary tree. At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.

If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output of this traversal, recover the tree and return its root.

Input & Output

Example 1 — Basic Tree

$ Input: traversal = "1-2--3--4-5"

› Output: [1,2,5,3,4,null,null]

💡 Note: Root 1 has children 2 and 5. Node 2 has children 3 and 4. The dashes indicate depth: 1 (depth 0), 2 (depth 1), 3 (depth 2), 4 (depth 2), 5 (depth 1).

Example 2 — Single Path

$ Input: traversal = "1-2--3---4"

› Output: [1,2,null,3,null,4]

💡 Note: Each node has only a left child, creating a left-skewed tree. Node 1 → 2 → 3 → 4 in a single path.

Example 3 — Single Node

$ Input: traversal = "1"

› Output: [1]

💡 Note: Only root node with value 1, no children.

Constraints

The number of nodes in the original tree is in the range [1, 1000]
1 ≤ Node.val ≤ 10⁹
The depth of any node is at most 1000

Visualization

Tap to expand

Understanding the Visualization

Input Format

String with dashes indicating depth and values

Parse Structure

Extract depth-value pairs from traversal

Build Tree

Construct binary tree using parent-child relationships

Key Takeaway

🎯 Key Insight: Stack depth mirrors tree depth - when moving to shallower levels, pop stack to find correct parent

Asked in

f Facebook 25 G Google 20 a Amazon 15

The key insight is to use a stack to maintain the path from root to current node, where stack depth corresponds to tree depth. The optimal approach parses the traversal string once to extract (depth, value) pairs, then uses a stack to track potential parent nodes. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Iterative Construction	O(n)	O(h)	Use stack to track parent nodes and build tree in single pass
Recursive Parsing with String Manipulation	O(n²)	O(n)	Parse each node by counting dashes and recursively process remaining string

Stack-Based Iterative Construction — Algorithm Steps

Parse traversal string to extract (depth, value) pairs
Use stack to maintain path from root to current node
For each new node, pop stack to find correct parent
Add node as left or right child based on parent's current state

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Input

Extract (depth, value) pairs from string

Stack Tracking

Maintain stack of potential parents

Tree Building

Attach nodes as left/right children

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct Node {
    int depth;
    int val;
};

struct TreeNode* solution(char* traversal) {
    if (!traversal || strlen(traversal) == 0) return NULL;
    
    // Parse the traversal string into (depth, value) pairs
    struct Node nodes[1000];
    int nodeCount = 0;
    int i = 0;
    int len = strlen(traversal);
    
    while (i < len) {
        int depth = 0;
        while (i < len && traversal[i] == '-') {
            depth++;
            i++;
        }
        
        // Parse the number
        int start = i;
        if (i < len && traversal[i] == '-') i++;
        while (i < len && isdigit(traversal[i])) {
            i++;
        }
        
        char temp = traversal[i];
        traversal[i] = '\0';
        int val = atoi(traversal + start);
        traversal[i] = temp;
        
        nodes[nodeCount].depth = depth;
        nodes[nodeCount].val = val;
        nodeCount++;
    }
    
    // Build tree using stack
    struct TreeNode* stack[1000];
    int stackSize = 0;
    
    for (int j = 0; j < nodeCount; j++) {
        struct TreeNode* treeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        treeNode->val = nodes[j].val;
        treeNode->left = NULL;
        treeNode->right = NULL;
        
        // Pop stack until we find the correct parent
        while (stackSize > nodes[j].depth) {
            stackSize--;
        }
        
        // If we have a parent, attach this node
        if (stackSize > 0) {
            struct TreeNode* parent = stack[stackSize - 1];
            if (parent->left == NULL) {
                parent->left = treeNode;
            } else {
                parent->right = treeNode;
            }
        }
        
        stack[stackSize++] = treeNode;
    }
    
    return stackSize > 0 ? stack[0] : NULL;
}

void printTreeArray(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    int values[1000];
    int count = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        
        if (node) {
            values[count++] = node->val;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            values[count++] = -1; // Use -1 to represent null
        }
    }
    
    // Remove trailing nulls
    while (count > 0 && values[count - 1] == -1) {
        count--;
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(",");
        if (values[i] == -1) {
            printf("null");
        } else {
            printf("%d", values[i]);
        }
    }
    printf("]\n");
}

int main() {
    char traversal[10000];
    fgets(traversal, sizeof(traversal), stdin);
    traversal[strcspn(traversal, "\n")] = 0;
    
    struct TreeNode* result = solution(traversal);
    printTreeArray(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the traversal string with constant time stack operations

✓ Linear Growth

Space Complexity

O(h)

Stack depth equals tree height, which can be up to n in worst case

✓ Linear Space

67.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Iterative Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler