Last updated on January 5th, 2025 at 01:12 am

Here, we see the Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution. This Leetcode problem is solved in many programming languages, such as C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Array, Depth-First Search, Tree

Companies

Bloomberg

Level of Question

Medium

Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution

1. 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 1:

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

Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Tree Depth First Search (DFS)”. This is because the code recursively traverses the tree in a depth-first manner to construct the binary tree from the given preorder and inorder traversal arrays.

3. Code Implementation in Different Languages

3.1 Construct Binary Tree from Preorder and Inorder Traversal C++

class Solution {
public:
    TreeNode* constructTree(vector < int > & preorder, int preStart, int preEnd, vector 
    < int > & inorder, int inStart, int inEnd, map < int, int > & mp) {
    if (preStart > preEnd || inStart > inEnd) return NULL;

    TreeNode* root = new TreeNode(preorder[preStart]);
    int elem = mp[root -> val];
    int nElem = elem - inStart;

    root -> left = constructTree(preorder, preStart + 1, preStart + nElem, inorder,
    inStart, elem - 1, mp);
    root -> right = constructTree(preorder, preStart + nElem + 1, preEnd, inorder, 
    elem + 1, inEnd, mp);

    return root;
    }

    TreeNode* buildTree(vector < int > & preorder, vector < int > & inorder) {
    int preStart = 0, preEnd = preorder.size() - 1;
    int inStart = 0, inEnd = inorder.size() - 1;

    map < int, int > mp;
    for (int i = inStart; i <= inEnd; i++) {
        mp[inorder[i]] = i;
    }

    return constructTree(preorder, preStart, preEnd, inorder, inStart, inEnd, mp);
    }
};

3.2 Construct Binary Tree from Preorder and Inorder Traversal Java

class Solution {
    private int i = 0;
    private int p = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }

    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (p >= preorder.length) {
            return null;
        }
        if (inorder[i] == stop) {
            ++i;
            return null;
        }
        TreeNode node = new TreeNode(preorder[p++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}

3.3 Construct Binary Tree from Preorder and Inorder Traversal JavaScript

var buildTree = function(preorder, inorder) {
    p = i = 0
    build = function(stop) {
        if (inorder[i] != stop) {
            var root = new TreeNode(preorder[p++])
            root.left = build(root.val)
            i++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};

3.4 Construct Binary Tree from Preorder and Inorder Traversal Python

class Solution(object):
    def buildTree(self, preorder, inorder):
        VAL_TO_INORDER_IDX = {inorder[i]: i for i in range(len(inorder))}
        def buildTreePartition(preorder, inorder_start, inorder_end):
            if not preorder or inorder_start < 0 or inorder_end > len(inorder):
                return None
            root_val = preorder[0]
            root_inorder_idx = VAL_TO_INORDER_IDX[root_val]
            if root_inorder_idx > inorder_end or root_inorder_idx < inorder_start:
                return None
            root = TreeNode(preorder.pop(0))
            root.left = buildTreePartition(preorder, inorder_start, root_inorder_idx - 1)
            root.right = buildTreePartition(preorder, root_inorder_idx + 1, inorder_end)
            return root
        return buildTreePartition(preorder, 0, len(inorder) - 1)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)