Last updated on October 5th, 2024 at 05:48 pm

Here, We see Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution

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]

1. Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution 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);
    }
};

2. Construct Binary Tree from Preorder and Inorder Traversal LeetCode Solution 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. Construct Binary Tree from Preorder and Inorder Traversal Solution 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()
};

4. Construct Binary Tree from Preorder and Inorder Traversal Solution 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)