Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal - Problem

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

You may assume that duplicates do not exist in the tree.

A binary tree can be uniquely determined by its inorder and postorder traversals because:

The last element in postorder 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

Input & Output

Example 1 — Basic Tree

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

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

💡 Note: The last element 3 in postorder is the root. In inorder, 3 splits the array: [9] (left subtree) and [15,20,7] (right subtree). Recursively apply the same logic.

Example 2 — Single Node

$ Input: inorder = [-1], postorder = [-1]

› Output: [-1]

💡 Note: Only one node, which is both root and the entire tree.

Example 3 — Linear Tree

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

› Output: [2,1,3]

💡 Note: Root is 2. In inorder: [1] is left subtree, [3] is right subtree. Creates a balanced tree with 2 as root.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: inorder [9,3,15,20,7] and postorder [9,15,7,20,3]

Key Insight

Last element of postorder (3) is root; inorder splits into left [9] and right [15,20,7]

Output

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

Key Takeaway

🎯 Key Insight: Postorder's last element reveals the root, inorder reveals the left/right split boundaries

Asked in

G Google 42 a Amazon 38 M Microsoft 35 f Facebook 28

The key insight is that postorder's last element is always the root, and inorder tells us which elements belong to left vs right subtrees. Best approach uses hash map optimization for O(1) root lookups. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursive	O(n²)	O(n)	Recursively find root in postorder, locate it in inorder, then split arrays
Hash Map Optimization	O(n)	O(n)	Pre-build hash map for O(1) inorder lookups, then use divide and conquer

Brute Force Recursive — Algorithm Steps

Step 1: Take last element of postorder as root
Step 2: Find root position in inorder by linear search
Step 3: Split arrays and recursively build left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Root

Last element of postorder is root

Locate in Inorder

Linear search to find root position

Split & Recurse

Divide arrays and build 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* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int findIndex(int* arr, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

struct TreeNode* solution(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    if (inorderSize == 0 || postorderSize == 0) {
        return NULL;
    }
    
    // Last element in postorder is the root
    int rootVal = postorder[postorderSize - 1];
    struct TreeNode* root = createNode(rootVal);
    
    // Find root position in inorder
    int rootIdx = findIndex(inorder, inorderSize, rootVal);
    
    // Recursively build subtrees
    root->left = solution(inorder, rootIdx, postorder, rootIdx);
    root->right = solution(inorder + rootIdx + 1, inorderSize - rootIdx - 1, 
                          postorder + rootIdx, postorderSize - rootIdx - 1);
    
    return root;
}

void printArray(int* arr, int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        if (i > 0) printf(",");
        printf("%d", arr[i]);
    }
    printf("]\n");
}

int main() {
    char line[1000];
    int inorder[100], postorder[100];
    int inorderSize = 0, postorderSize = 0;
    
    // Parse inorder
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            inorder[inorderSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse postorder
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            postorder[postorderSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct TreeNode* result = solution(inorder, inorderSize, postorder, postorderSize);
    
    // Simple output - just print first few values for demonstration
    printf("[%d]\n", result ? result->val : 0);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform O(n) linear search in inorder array

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion call stack depth can be O(n) in worst case (skewed tree)

⚡ Linearithmic Space

287.6K Views

High Frequency

~25 min Avg. Time

3.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

Brute Force Recursive — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler