889. Construct Binary Tree from Pre & Postorder - Solution

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

Example 1:

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]

Example 2:

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

Constraints:

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
All the values of preorder are unique.
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
All the values of postorder are unique.
It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Approach overview

Problem Overview: You receive two arrays representing the preorder and postorder traversal of a binary tree. The task is to reconstruct any valid binary tree that produces these traversals. Since preorder processes root → left → right and postorder processes left → right → root, the root is easy to identify but determining subtree boundaries requires careful indexing.

Approach 1: Recursive Construction by Dividing Preorder and Postorder Arrays (O(n²) time, O(h) space)

This method builds the tree using recursive partitioning of the traversal arrays. The first value in preorder is always the root. The next value in preorder represents the left subtree's root. Search for this value in the postorder array to determine how many nodes belong to the left subtree. Once you know the subtree size, recursively construct the left and right children using sliced index ranges of both arrays. The logic mirrors how preorder and postorder traverse the tree. However, repeatedly scanning the postorder array to locate subtree boundaries leads to O(n²) time in the worst case, especially for skewed trees. Space complexity is O(h) from recursion depth where h is tree height.

Approach 2: Recursive Approach with Hash Map Optimization (O(n) time, O(n) space)

The optimization removes repeated searches in the postorder array. Before recursion, build a hash map from node value to its index in postorder. Now when preorder identifies the root and the next value as the left subtree root, you can find its position in O(1) using a hash lookup. That index directly tells you the size of the left subtree. Recursively build left and right subtrees using index boundaries without copying arrays. Each node is processed once, giving O(n) time complexity. The map requires O(n) space and recursion still uses O(h) stack space. This approach fits naturally with divide and conquer recursion and efficient indexing.

The solution relies heavily on traversal properties of a tree and the structure of a binary tree. Preorder always exposes the root first, while postorder reveals subtree completion. Combining both lets you reconstruct subtree boundaries.

Recommended for interviews: The hash map optimized recursive approach. Interviewers expect you to recognize that repeated index searches are inefficient and replace them with constant‑time lookups. Implementing the plain recursive partition first shows understanding of traversal relationships, while the optimized version demonstrates algorithmic maturity and time complexity awareness.

Approach 1: Recursive Construction by Dividing Preorder and Postorder Arrays

This approach involves recursively dividing the preorder and postorder arrays to construct the tree. The first element of the preorder array is the root of the tree. The left subtree can be determined by identifying the position of the second element in preorder in the postorder array. Recursively apply this strategy for each subtree.

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        if not preorder or not postorder:
            return None
        root = TreeNode(preorder[0])
        if len(preorder) == 1:
            return root
        # Find left subtree from postorder[0] to the element position which is previous of root in postorder
        L = postorder.index(preorder[1]) + 1
        root.left = self.constructFromPrePost(preorder[1:L + 1], postorder[:L])
        root.right = self.constructFromPrePost(preorder[L + 1:], postorder[L:-1])
        return root

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int preIndex = 0;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return buildTree(preorder, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] postorder, int l, int r) {
        if (l > r) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex++]);
        if (l == r) {
            return root;
        }
        int i;
        for (i = l; i <= r; i++) {
            if (postorder[i] == preorder[preIndex]) {
                break;
            }
        }
        root.left = buildTree(preorder, postorder, l, i);
        root.right = buildTree(preorder, postorder, i + 1, r - 1);
        return root;
    }
}

C++

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        index = 0;
        return buildTree(preorder, postorder, 0, postorder.size() - 1);
    }

private:
    int index;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& postorder, int l, int r) {
        if (l > r) return nullptr;
        TreeNode* root = new TreeNode(preorder[index++]);
        if (l == r) return root;
        int i;
        for (i = l; i <= r; ++i)
            if (postorder[i] == preorder[index]) break;
        root->left = buildTree(preorder, postorder, l, i);
        root->right = buildTree(preorder, postorder, i + 1, r - 1);
        return root;
    }
};

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var constructFromPrePost = function(preorder, postorder) {
    let preIndex = 0;
    const buildTree = (l, r) => {
        if (l > r) return null;
        const root = new TreeNode(preorder[preIndex++]);
        if (l == r) return root;
        let i;
        for (i = l; i <= r; ++i) {
            if (postorder[i] == preorder[preIndex]) break;
        }
        root.left = buildTree(l, i);
        root.right = buildTree(i + 1, r - 1);
        return root;
    };
    return buildTree(0, postorder.length - 1);
};

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private int preIndex = 0;
    public TreeNode ConstructFromPrePost(int[] preorder, int[] postorder) {
        return BuildTree(preorder, postorder, 0, postorder.Length - 1);
    }

    private TreeNode BuildTree(int[] preorder, int[] postorder, int l, int r) {
        if (l > r) return null;
        TreeNode root = new TreeNode(preorder[preIndex++]);
        if (l == r) return root;
        int i;
        for (i = l; i <= r; i++) {
            if (postorder[i] == preorder[preIndex]) break;
        }
        root.left = BuildTree(preorder, postorder, l, i);
        root.right = BuildTree(preorder, postorder, i + 1, r - 1);
        return root;
    }
}

This solution defines the TreeNode class and implements a recursive method constructFromPrePost. The method splits the preorder and postorder lists to find left and right subtrees, creating TreeNode objects recursively. The base case checks for empty lists, indicating no subtree exists, thus returning None.

Complexity

Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive.

Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes.

Try this approach in the editor

Approach 2: Recursive Approach with Hash Map Optimization

This method optimizes the naive recursive approach by using a hash map to store the indices of values in the postorder sequence. By doing so, we can quickly find the index of the next root node, reducing the time complexity significantly. This way, the subtrees can be constructed in a more efficient manner by avoiding repeated searches.

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        post_index_map = {value: i for i, value in enumerate(postorder)}
        pre_index = 0

        def construct(l, r):
            nonlocal pre_index
            if l > r:
                return None
            root_val = preorder[pre_index]
            root = TreeNode(root_val)
            pre_index += 1
            if l == r:
                return root
            left_root_val = preorder[pre_index]
            post_index = post_index_map[left_root_val]
            root.left = construct(l, post_index)
            root.right = construct(post_index + 1, r - 1)
            return root

        return construct(0, len(postorder) - 1)

Java

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int preIndex = 0;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        HashMap<Integer, Integer> postIndexMap = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            postIndexMap.put(postorder[i], i);
        }
        return buildTree(preorder, postIndexMap, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, HashMap<Integer, Integer> postIndexMap, int l, int r) {
        if (l > r) {
            return null;
        }
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        if (l == r) {
            return root;
        }
        int leftRootVal = preorder[preIndex];
        int postIndex = postIndexMap.get(leftRootVal);
        root.left = buildTree(preorder, postIndexMap, l, postIndex);
        root.right = buildTree(preorder, postIndexMap, postIndex + 1, r - 1);
        return root;
    }
}

C++

#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        unordered_map<int, int> post_index_map;
        for (int i = 0; i < postorder.size(); ++i) {
            post_index_map[postorder[i]] = i;
        }
        int preIndex = 0;
        return buildTree(preorder, post_index_map, 0, postorder.size() - 1, preIndex);
    }

private:
    TreeNode* buildTree(vector<int>& preorder, unordered_map<int, int>& post_index_map, int l, int r, int& preIndex) {
        if (l > r) return nullptr;
        TreeNode* root = new TreeNode(preorder[preIndex++]);
        if (l == r) return root;
        int leftRootVal = preorder[preIndex];
        int postIndex = post_index_map[leftRootVal];
        root->left = buildTree(preorder, post_index_map, l, postIndex, preIndex);
        root->right = buildTree(preorder, post_index_map, postIndex + 1, r - 1, preIndex);
        return root;
    }
};

JavaScript

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var constructFromPrePost = function(preorder, postorder) {
    let preIndex = 0;
    const postMap = new Map(postorder.map((val, idx) => [val, idx]));

    const buildTree = (l, r) => {
        if (l > r) return null;
        const root = new TreeNode(preorder[preIndex++]);
        if (l === r) return root;
        let leftRootVal = preorder[preIndex];
        let postIndex = postMap.get(leftRootVal);
        root.left = buildTree(l, postIndex);
        root.right = buildTree(postIndex + 1, r - 1);
        return root;
    };

    return buildTree(0, postorder.length - 1);
};

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private int preIndex = 0;
    public TreeNode ConstructFromPrePost(int[] preorder, int[] postorder) {
        Dictionary<int, int> postIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < postorder.Length; i++) {
            postIndexMap[postorder[i]] = i;
        }
        return BuildTree(preorder, postIndexMap, 0, postorder.Length - 1);
    }

    private TreeNode BuildTree(int[] preorder, Dictionary<int, int> postIndexMap, int l, int r) {
        if (l > r) return null;
        TreeNode root = new TreeNode(preorder[preIndex++]);
        if (l == r) return root;
        int leftRootVal = preorder[preIndex];
        int postIndex = postIndexMap[leftRootVal];
        root.left = BuildTree(preorder, postIndexMap, l, postIndex);
        root.right = BuildTree(preorder, postIndexMap, postIndex + 1, r - 1);
        return root;
    }
}

The optimized Python approach uses a hash map to store the values and their indices in the postorder sequence. This allows for O(1) time complexity for querying indices in the postorder array. The recursive construct method builds the tree using the preIndex to track root values in preorder.

Complexity

Time Complexity: O(n) - Hash map optimization reduces the search time significantly.

Space Complexity: O(n) - Due to the hash map and recursion stack.

Try this approach in the editor

Approach 3: Recursion

The order of pre-order traversal is: root node -> left subtree -> right subtree, and the order of post-order traversal is: left subtree -> right subtree -> root node.

Therefore, the root node of the binary tree must be the first node of the pre-order traversal and the last node of the post-order traversal.

Next, we need to determine the range of the left and right subtrees of the binary tree.

If the binary tree has a left subtree, then the root node of the left subtree must be the second node of the pre-order traversal; if the binary tree does not have a left subtree, then the second node of the pre-order traversal must be the root node of the right subtree. Since the results of post-order traversal in these two cases are the same, we can take the second node of the pre-order traversal as the root node of the left subtree, and then find its position in the post-order traversal, so as to determine the range of the left subtree.

Specifically, we design a recursive function dfs(a, b, c, d), where [a, b] represents the range of pre-order traversal, and [c, d] represents the range of post-order traversal. The function of this function is to construct the root node of the binary tree based on the pre-order traversal [a, b] and the post-order traversal [c, d]. The answer is dfs(0, n - 1, 0, n - 1), where n is the length of the pre-order traversal.

The execution steps of the function dfs(a, b, c, d) are as follows:

If a > b, the range is empty, return a null node directly.
Otherwise, we construct a new node root, its value is the value of the first node in the pre-order traversal, which is preorder[a].
If a equals b, it means that root has neither a left subtree nor a right subtree, return root directly.
Otherwise, the value of the root node of the left subtree is preorder[a + 1], we find the position of preorder[a + 1] in the post-order traversal, denoted as i. The number of nodes in the left subtree m = i - c + 1, from this we know that the range of the left subtree in the pre-order traversal is [a + 1, a + m], the range in the post-order traversal is [c, i], the range of the right subtree in the pre-order traversal is [a + m + 1, b], and the range in the post-order traversal is [i + 1, d - 1].
Knowing the range of the left and right subtrees, we can recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees as the left and right child nodes of root respectively. Finally return root.

In the function dfs(a, b, c, d), we need to use a hash table pos, which stores the position of each node in the post-order traversal. At the beginning of the function, we can calculate this hash table first, so that we can find the position of any node in the post-order traversal in O(1) time.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
    const pos: Map<number, number> = new Map();
    const n = postorder.length;
    for (let i = 0; i < n; ++i) {
        pos.set(postorder[i], i);
    }
    const dfs = (a: number, b: number, c: number, d: number): TreeNode | null => {
        if (a > b) {
            return null;
        }
        const root = new TreeNode(preorder[a]);
        if (a === b) {
            return root;
        }
        const i = pos.get(preorder[a + 1])!;
        const m = i - c + 1;
        root.left = dfs(a + 1, a + m, c, i);
        root.right = dfs(a + m + 1, b, i + 1, d - 1);
        return root;
    };
    return dfs(0, n - 1, 0, n - 1);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	pos := map[int]int{}
	for i, x := range postorder {
		pos[x] = i
	}
	var dfs func(int, int, int, int) *TreeNode
	dfs = func(a, b, c, d int) *TreeNode {
		if a > b {
			return nil
		}
		root := &TreeNode{Val: preorder[a]}
		if a == b {
			return root
		}
		i := pos[preorder[a+1]]
		m := i - c + 1
		root.Left = dfs(a+1, a+m, c, i)
		root.Right = dfs(a+m+1, b, i+1, d-1)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}

Try this approach in the editor

Approach 4: Another Recursive Approach

We can design a recursive function dfs(i, j, n), where i and j represent the starting points of the pre-order and post-order traversals, respectively, and n represents the number of nodes. This function constructs the root node of the binary tree based on the pre-order traversal [i, i + n - 1] and post-order traversal [j, j + n - 1]. The answer is dfs(0, 0, n), where n is the length of the pre-order traversal.

The execution steps of the function dfs(i, j, n) are as follows:

If n = 0, the range is empty, so return a null node directly.
Otherwise, we construct a new node root, whose value is the value of the first node in the pre-order traversal, which is preorder[i].
If n = 1, it means that root has neither a left subtree nor a right subtree, so return root directly.
Otherwise, the value of the root node of the left subtree is preorder[i + 1]. We find the position of preorder[i + 1] in the post-order traversal, denoted as k. Then the number of nodes in the left subtree is m = k - j + 1, and the number of nodes in the right subtree is n - m - 1. We recursively rebuild the left and right subtrees, and then make the root nodes of the left and right subtrees the left and right child nodes of root, respectively. Finally, return root.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function constructFromPrePost(preorder: number[], postorder: number[]): TreeNode | null {
    const pos: Map<number, number> = new Map();
    const n = postorder.length;
    for (let i = 0; i < n; ++i) {
        pos.set(postorder[i], i);
    }
    const dfs = (i: number, j: number, n: number): TreeNode | null => {
        if (n <= 0) {
            return null;
        }
        const root = new TreeNode(preorder[i]);
        if (n === 1) {
            return root;
        }
        const k = pos.get(preorder[i + 1])!;
        const m = k - j + 1;
        root.left = dfs(i + 1, j, m);
        root.right = dfs(i + 1 + m, k + 1, n - 1 - m);
        return root;
    };
    return dfs(0, 0, n);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
	pos := map[int]int{}
	for i, x := range postorder {
		pos[x] = i
	}
	var dfs func(int, int, int) *TreeNode
	dfs = func(i, j, n int) *TreeNode {
		if n <= 0 {
			return nil
		}
		root := &TreeNode{Val: preorder[i]}
		if n == 1 {
			return root
		}
		k := pos[preorder[i+1]]
		m := k - j + 1
		root.Left = dfs(i+1, j, m)
		root.Right = dfs(i+m+1, k+1, n-m-1)
		return root
	}
	return dfs(0, 0, len(preorder))
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Construction by Dividing Preorder and Postorder Arrays	Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive. Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes.
Recursive Approach with Hash Map Optimization	Time Complexity: O(n) - Hash map optimization reduces the search time significantly. Space Complexity: O(n) - Due to the hash map and recursion stack.
Recursion	–
Another Recursive Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Construction by Dividing Arrays	O(n²)	O(h)	Useful for understanding traversal relationships and simple recursive reconstruction logic
Recursive Approach with Hash Map Optimization	O(n)	O(n)	Preferred for interviews and large inputs where repeated searches must be avoided

Frequently asked questions

Is Construct Binary Tree from Preorder and Postorder Traversal easy or hard?

The problem is rated Medium because identifying the root is simple but determining subtree boundaries requires understanding how preorder and postorder interact. Once you recognize that the second preorder element marks the left subtree root, the divide‑and‑conquer recursion becomes straightforward.

Construct Binary Tree from Preorder and Postorder Traversal Python/Java solution

Python, Java, C++, C#, and JavaScript implementations typically follow the same recursive structure. The function tracks preorder and postorder index ranges, constructs the root, finds the left subtree size using a hash map, and recursively builds the children. Each language version runs in O(n) time with O(n) extra space.

How to solve Construct Binary Tree from Preorder and Postorder Traversal in O(n)?

Create a hash map from node value to its index in the postorder traversal. During recursion, use preorder to identify the root and the left subtree root. The hash map gives the left subtree boundary instantly, allowing you to split the traversal ranges and build the tree recursively in linear time.

What is the best approach for Construct Binary Tree from Preorder and Postorder Traversal?

The most efficient approach uses recursion with a hash map that stores the index of each value in the postorder traversal. Preorder gives the root immediately, and the next preorder value identifies the left subtree root. A hash lookup determines the subtree size in O(1), allowing the tree to be built recursively in O(n) time.

Is Construct Binary Tree from Preorder and Postorder Traversal asked at Google/Amazon/Meta?

Binary tree reconstruction problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. Variants include building trees from inorder + preorder or inorder + postorder. This version tests understanding of traversal properties and recursive divide and conquer.

What data structure is used in Construct Binary Tree from Preorder and Postorder Traversal?

The core data structure is a binary tree built through recursive calls. An auxiliary hash map is commonly used to store postorder indices for constant‑time lookup. The algorithm also relies on array indexing and divide‑and‑conquer recursion.

What is the time complexity of Construct Binary Tree from Preorder and Postorder Traversal?

The optimized solution runs in O(n) time because each node is processed once and subtree boundaries are found using constant‑time hash lookups. A simpler version that scans the postorder array for each subtree takes O(n²) in the worst case. Space complexity is O(n) for the hash map plus recursion stack.

Construct Binary Tree from Preorder and Postorder Traversal solution and explanation

The problem

Approach overview

Approach 1: Recursive Construction by Dividing Preorder and Postorder Arrays

Approach 2: Recursive Approach with Hash Map Optimization

Approach 3: Recursion

Approach 4: Another Recursive Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct Binary Tree from Preorder and Postorder Traversal solution and explanation

The problem

Approach overview

Approach 1: Recursive Construction by Dividing Preorder and Postorder Arrays

Approach 2: Recursive Approach with Hash Map Optimization

Approach 3: Recursion

Approach 4: Another Recursive Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems