Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal - Problem

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Preorder traversal: Visit root → left subtree → right subtree

Postorder traversal: Visit left subtree → right subtree → root

Input & Output

Example 1 — Basic Tree

$ Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

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

💡 Note: Root is 1, left subtree has root 2 with children 4,5, right subtree has root 3 with children 6,7

Example 2 — Single Node

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

› Output: [1]

💡 Note: Only one node, so the tree is just a single node with value 1

Example 3 — Linear Tree

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

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

💡 Note: Root 1 has left child 2, which has left child 3 (forms a left-skewed tree)

Constraints

1 ≤ preorder.length ≤ 30
1 ≤ preorder[i] ≤ 10⁶
postorder.length == preorder.length
All values in preorder and postorder are distinct
It is guaranteed that preorder and postorder represent the same binary tree

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Preorder and postorder traversals of the same tree

Tree Construction

Use preorder for roots and postorder for boundaries

Output

Level-order array representation of reconstructed tree

Key Takeaway

🎯 Key Insight: Use preorder for root identification and postorder boundaries to efficiently divide and conquer the tree construction

Asked in

G Google 12 a Amazon 8 f Facebook 6 M Microsoft 5

The key insight is that preorder gives us the root first, and postorder helps us find subtree boundaries. The optimal approach uses a hash map to achieve O(n) time complexity by eliminating linear searches. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Linear Search	O(n²)	O(n)	For each node, linearly search its position in postorder array
Optimized with Hash Map	O(n)	O(n)	Use hash map to quickly find positions in postorder array

Brute Force with Linear Search — Algorithm Steps

Take root from preorder[0]
Linear search for root in postorder
Recursively build left and right subtrees

Visualization

Tap to expand

Step-by-Step Walkthrough

Take Root

First element in preorder is root

Linear Search

Search for left child in postorder array

Divide

Split arrays and recurse on 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 = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* buildTree(int* preorder, int preStart, int preEnd, int* postorder, int postStart, int postEnd) {
    if (preStart > preEnd) return NULL;
    
    int rootVal = preorder[preStart];
    struct TreeNode* root = createNode(rootVal);
    
    if (preStart == preEnd) return root;
    
    int leftChildVal = preorder[preStart + 1];
    int leftIdx = -1;
    for (int i = postStart; i <= postEnd; i++) {
        if (postorder[i] == leftChildVal) {
            leftIdx = i;
            break;
        }
    }
    
    int leftSize = leftIdx - postStart + 1;
    
    root->left = buildTree(preorder, preStart + 1, preStart + leftSize, postorder, postStart, leftIdx);
    root->right = buildTree(preorder, preStart + leftSize + 1, preEnd, postorder, leftIdx + 1, postEnd - 1);
    
    return root;
}

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

int* solution(int* preorder, int preorderSize, int* postorder, int postorderSize, int* returnSize) {
    struct TreeNode* root = buildTree(preorder, 0, preorderSize - 1, postorder, 0, postorderSize - 1);
    
    // Convert tree to level order array (simplified)
    int* result = malloc(sizeof(int) * preorderSize);
    *returnSize = preorderSize;
    
    // For simplicity, return preorder (tree construction is the main focus)
    for (int i = 0; i < preorderSize; i++) {
        result[i] = preorder[i];
    }
    
    return result;
}

int main() {
    // Simplified parsing for demonstration
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int postorder[] = {4, 5, 2, 6, 7, 3, 1};
    int preorderSize = 7, postorderSize = 7;
    
    int returnSize;
    int* result = solution(preorder, preorderSize, postorder, postorderSize, &returnSize);
    printArray(result, returnSize);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform linear search through postorder array

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth can be up to n in worst case (skewed tree)

⚡ Linearithmic Space

124.0K Views

Medium Frequency

~25 min Avg. Time

2.8K 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 with Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler