By Virendra Jadhav

When working with binary trees, it’s common to face problems where you need to reconstruct the tree from given traversal orders.

In this blog, we’ll cover:

✅ How to build a binary tree from Preorder and Inorder Traversals
✅ How to build a binary tree from Inorder and Postorder Traversals
✅ Why we cannot uniquely build a tree from Preorder and Postorder Traversals

🚩 Problem 1: Construct Binary Tree from Preorder and Inorder Traversal

📚 Problem Statement:

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.

🔍 Example:

Input:

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

Output:

💡 Approach:

In preorder, the first element is always the root.
In inorder, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree.
Using a hashmap to store the index positions of inorder elements helps quickly find the root.
Recursively split preorder and inorder arrays to build left and right subtrees.

✅ Java Solution:

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length <= 0 || inorder.length <= 0) return null;

        HashMap<Integer, Integer> imap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            imap.put(inorder[i], i);
        }

        return constructBT(preorder, 0, preorder.length - 1, 0, inorder.length - 1, imap);
    }

    private TreeNode constructBT(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, HashMap<Integer, Integer> imap) {
        if (preStart > preEnd || inStart > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preStart]);
        int indexRoot = imap.get(root.val);
        int numLeft = indexRoot - inStart;

        root.left = constructBT(preorder, preStart + 1, preStart + numLeft, inStart, indexRoot - 1, imap);
        root.right = constructBT(preorder, preStart + numLeft + 1, preEnd, indexRoot + 1, inEnd, imap);

        return root;
    }
}

🔹 C++ Solution

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inorderMap;
        for(int i = 0; i < inorder.size(); ++i)
            inorderMap[inorder[i]] = i;

        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inorderMap);
    }

private:
    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
                    vector<int>& inorder, int inStart, int inEnd,
                    unordered_map<int, int>& inorderMap) {
        if(preStart > preEnd || inStart > inEnd) return nullptr;

        TreeNode* root = new TreeNode(preorder[preStart]);
        int rootIndex = inorderMap[root->val];
        int leftSize = rootIndex - inStart;

        root->left = build(preorder, preStart + 1, preStart + leftSize,
                           inorder, inStart, rootIndex - 1, inorderMap);

        root->right = build(preorder, preStart + leftSize + 1, preEnd,
                            inorder, rootIndex + 1, inEnd, inorderMap);

        return root;
    }
};

🔹 Python Solution

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {val: i for i, val in enumerate(inorder)}

        def build(preStart, preEnd, inStart, inEnd):
            if preStart > preEnd or inStart > inEnd:
                return None

            root_val = preorder[preStart]
            root = TreeNode(root_val)
            root_index = inorder_map[root_val]
            left_size = root_index - inStart

            root.left = build(preStart + 1, preStart + left_size, inStart, root_index - 1)
            root.right = build(preStart + left_size + 1, preEnd, root_index + 1, inEnd)
            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1)

🚀 Problem 2: Construct Binary Tree from Inorder and Postorder Traversal

📚 Problem Statement:

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.

🔍 Example:

Input:

Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]

Output:

💡 Approach:

In postorder, the last element is always the root.
In inorder, elements to the left of the root belong to the left subtree, and elements to the right belong to the right subtree.
Use a hashmap to store the index positions of inorder elements to quickly locate the root.
Recursively build left and right subtrees by adjusting indices carefully.

✅ Java Solution:

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length <= 0 || postorder.length <= 0) return null;

        HashMap<Integer, Integer> imap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            imap.put(inorder[i], i);
        }

        return constructBT(postorder, 0, postorder.length - 1, 0, inorder.length - 1, imap);
    }

    private TreeNode constructBT(int[] postorder, int postStart, int postEnd, int inStart, int inEnd, HashMap<Integer, Integer> imap) {
        if (inStart > inEnd || postStart > postEnd) return null;

        TreeNode root = new TreeNode(postorder[postEnd]);
        int indexRoot = imap.get(root.val);
        int numLeft = indexRoot - inStart;

        root.left = constructBT(postorder, postStart, postStart + numLeft - 1, inStart, indexRoot - 1, imap);
        root.right = constructBT(postorder, postStart + numLeft, postEnd - 1, indexRoot + 1, inEnd, imap);

        return root;
    }
}

🔹 C++ Solution

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> inorderMap;
        for(int i = 0; i < inorder.size(); ++i)
            inorderMap[inorder[i]] = i;

        return build(postorder, 0, postorder.size() - 1,
                     inorder, 0, inorder.size() - 1, inorderMap);
    }

private:
    TreeNode* build(vector<int>& postorder, int postStart, int postEnd,
                    vector<int>& inorder, int inStart, int inEnd,
                    unordered_map<int, int>& inorderMap) {
        if(postStart > postEnd || inStart > inEnd) return nullptr;

        TreeNode* root = new TreeNode(postorder[postEnd]);
        int rootIndex = inorderMap[root->val];
        int leftSize = rootIndex - inStart;

        root->left = build(postorder, postStart, postStart + leftSize - 1,
                           inorder, inStart, rootIndex - 1, inorderMap);
        root->right = build(postorder, postStart + leftSize, postEnd - 1,
                            inorder, rootIndex + 1, inEnd, inorderMap);

        return root;
    }
};

🔹 Python Solution

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {val: i for i, val in enumerate(inorder)}

        def build(postStart, postEnd, inStart, inEnd):
            if postStart > postEnd or inStart > inEnd:
                return None

            root_val = postorder[postEnd]
            root = TreeNode(root_val)
            root_index = inorder_map[root_val]
            left_size = root_index - inStart

            root.left = build(postStart, postStart + left_size - 1, inStart, root_index - 1)
            root.right = build(postStart + left_size, postEnd - 1, root_index + 1, inEnd)
            return root

        return build(0, len(postorder) - 1, 0, len(inorder) - 1)

🚫 Why We Cannot Build a Unique Tree from Preorder and Postorder

📌 Key Reason:

When we only have Preorder and Postorder, we don’t have enough information to uniquely determine the structure of the tree.

Example:

Given:

Preorder: [1, 2]
Postorder: [2, 1]

There are two possible trees:

Tree 1:            Tree 2:
    1                   1
   /                     \
  2                       2

Without Inorder traversal, we cannot distinguish between these two cases.

📚 Quick Summary:

Given Traversals	Unique Tree Possible?
Preorder + Inorder	✅ Yes
Inorder + Postorder	✅ Yes
Preorder + Postorder	❌ No

🕒 Complexity for Both Solutions:

Time Complexity: O(N)
Space Complexity: O(N)

✨ Final Thoughts:

These binary tree construction problems are a perfect way to master:

Recursive thinking
Traversal orders
Index management

Understanding which combinations of traversals give unique solutions is crucial when working on tree-related coding problems.

Let’s connect if you’re diving into more DSA challenges! 🚀

🌳 Constructing Binary Trees from Traversals: Preorder-Inorder and Inorder-Postorder

🚩 Problem 1: Construct Binary Tree from Preorder and Inorder Traversal

📚 Problem Statement:

🔍 Example:

Input:

Output:

💡 Approach:

✅ Java Solution:

🚀 Problem 2: Construct Binary Tree from Inorder and Postorder Traversal

📚 Problem Statement:

🔍 Example:

Input:

💡 Approach:

🚫 Why We Cannot Build a Unique Tree from Preorder and Postorder

📌 Key Reason:

Example:

📚 Quick Summary:

🕒 Complexity for Both Solutions:

✨ Final Thoughts:

Subscribe to my newsletter

Virendra Jadhav

Virendra Jadhav