Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal - Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Key insights:

The first element in preorder is always the root
Elements to the left of root in inorder form the left subtree
Elements to the right of root in inorder form the right subtree
We can recursively apply this pattern to build the entire tree

Input & Output

Example 1 — Basic Tree

$ Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

› Output: [3,9,20,null,null,15,7]

💡 Note: Root is 3 (first in preorder). In inorder, 9 is left subtree, [15,20,7] is right subtree. Recursively build: left child 9, right child 20 with children 15,7.

Example 2 — Linear Tree

$ Input: preorder = [1,2,3], inorder = [3,2,1]

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

💡 Note: Root 1, left subtree [3,2], no right. Root 2 has left child 3. Forms a left-leaning tree.

Example 3 — Single Node

$ Input: preorder = [1], inorder = [1]

› Output: [1]

💡 Note: Single node tree - root is 1 with no children.

Constraints

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
-3000 ≤ preorder[i], inorder[i] ≤ 3000
preorder and inorder consist of unique values
Each value of inorder also appears in preorder
preorder is guaranteed to be the preorder traversal of the tree
inorder is guaranteed to be the inorder traversal of the same tree

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Preorder [3,9,20,15,7] and Inorder [9,3,15,20,7]

Pattern Recognition

First in preorder = root, inorder splits subtrees

Tree Output

Reconstructed binary tree [3,9,20,null,null,15,7]

Key Takeaway

🎯 Key Insight: Preorder gives root order, inorder reveals left/right subtree boundaries

Asked in

f Facebook 45 A Amazon 38 G Google 32 M Microsoft 28

The key insight is that preorder's first element is always the root, and inorder splits left/right subtrees. Best approach uses HashMap optimization for O(1) root lookups. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Linear Search	O(n²)	O(n)	Recursively find root in inorder array using linear search to split subtrees
HashMap Optimization	O(n)	O(n)	Use HashMap to store inorder indices for O(1) root lookup, avoiding repeated linear searches

Recursive with Linear Search — Algorithm Steps

Step 1: Take first element from preorder as root
Step 2: Find root position in inorder using linear search
Step 3: Split inorder into left and right parts
Step 4: Recursively build left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Root

Take first from preorder, find in inorder

Split Arrays

Divide based on root position

Recurse

Build left and right subtrees

Code -

solution.c — C

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

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

struct TreeNode* solution(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0) return NULL;
    
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = preorder[0];
    root->left = NULL;
    root->right = NULL;
    
    int rootIdx = 0;
    for (int i = 0; i < inorderSize; i++) {
        if (inorder[i] == preorder[0]) {
            rootIdx = i;
            break;
        }
    }
    
    root->left = solution(preorder + 1, rootIdx, inorder, rootIdx);
    root->right = solution(preorder + rootIdx + 1, preorderSize - rootIdx - 1, 
                          inorder + rootIdx + 1, inorderSize - rootIdx - 1);
    
    return root;
}

void printTreeArray(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    int result[1000];
    int resultSize = 0;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            result[resultSize++] = node->val;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        }
    }
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("%d", result[i]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
}

int main() {
    char line[1000];
    int preorder[1000], inorder[1000];
    int preorderSize = 0, inorderSize = 0;
    
    // Read preorder
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]\n");
    while (token) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            preorder[preorderSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    // Read inorder
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]\n");
    while (token) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            inorder[inorderSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    struct TreeNode* result = solution(preorder, preorderSize, inorder, inorderSize);
    printTreeArray(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of n nodes requires O(n) linear search in inorder array

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n nodes plus tree storage

⚡ Linearithmic Space

239.2K Views

High Frequency

~25 min Avg. Time

8.5K 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

Recursive with Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler