Construct Binary Tree from Preorder and Inorder Traversal solution and explanation

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

class Solution:
    def buildTree(self, preorder, inorder):
        def helper(preorder_start, preorder_end, inorder_start, inorder_end):
            if preorder_start > preorder_end:
                return None

            root_val = preorder[preorder_start]
            root = TreeNode(root_val)
            inorder_root_index = inorder_index_map[root_val]
            left_tree_size = inorder_root_index - inorder_start

            root.left = helper(preorder_start + 1, preorder_start + left_tree_size, inorder_start, inorder_root_index - 1)
            root.right = helper(preorder_start + left_tree_size + 1, preorder_end, inorder_root_index + 1, inorder_end)

            return root

        inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
        n = len(preorder)
        return helper(0, n - 1, 0, n - 1)

import java.util.HashMap;
import java.util.Map;

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

    private Map<Integer, Integer> inorderIndexMap;
    private int preorderIndex;

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

    private TreeNode buildTree(int[] preorder, int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd) {
            return null;
        }

        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        int inorderRootIndex = inorderIndexMap.get(rootVal);

        root.left = buildTree(preorder, inorderStart, inorderRootIndex - 1);
        root.right = buildTree(preorder, inorderRootIndex + 1, inorderEnd);

        return root;
    }
}

#include <unordered_map>
#include <vector>
#include <stack>

using namespace std;

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;

        unordered_map<int, int> inorderIndexMap;
        for (int i = 0; i < inorder.size(); ++i) {
            inorderIndexMap[inorder[i]] = i;
        }

        stack<TreeNode*> st;
        TreeNode* root = new TreeNode(preorder[0]);
        st.push(root);
        int inorderIndex = 0;

        for (int i = 1; i < preorder.size(); ++i) {
            TreeNode* node = st.top();
            if (inorderIndexMap[node->val] != inorderIndex) {
                node->left = new TreeNode(preorder[i]);
                st.push(node->left);
            } else {
                while (!st.empty() && inorderIndexMap[st.top()->val] == inorderIndex) {
                    node = st.top();
                    st.pop();
                    ++inorderIndex;
                }
                node->right = new TreeNode(preorder[i]);
                st.push(node->right);
            }
        }

        return root;
    }
};

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

var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) return null;

    const inorderIndexMap = {};
    inorder.forEach((val, idx) => {
        inorderIndexMap[val] = idx;
    });

    const stack = [];
    const root = new TreeNode(preorder[0]);
    stack.push(root);
    let inorderIndex = 0;

    for (let i = 1; i < preorder.length; i++) {
        let node = stack[stack.length - 1];
        if (inorderIndexMap[node.val] !== inorderIndex) {
            node.left = new TreeNode(preorder[i]);
            stack.push(node.left);
        } else {
            while (stack.length && inorderIndexMap[stack[stack.length - 1].val] === inorderIndex) {
                node = stack.pop();
                inorderIndex++;
            }
            node.right = new TreeNode(preorder[i]);
            stack.push(node.right);
        }
    }

    return root;
};

/**
 * 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 buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const d: Map<number, number> = new Map();
    const n = inorder.length;
    for (let i = 0; i < n; ++i) {
        d.set(inorder[i], i);
    }
    const dfs = (i: number, j: number, n: number): TreeNode | null => {
        if (n <= 0) {
            return null;
        }
        const v = preorder[i];
        const k = d.get(v)!;
        const l = dfs(i + 1, j, k - j);
        const r = dfs(i + 1 + k - j, k + 1, n - 1 - (k - j));
        return new TreeNode(v, l, r);
    };
    return dfs(0, 0, n);
}

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

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut d = HashMap::new();
        for (i, &x) in inorder.iter().enumerate() {
            d.insert(x, i);
        }
        Self::dfs(&preorder, &d, 0, 0, preorder.len())
    }

    pub fn dfs(
        preorder: &Vec<i32>,
        d: &HashMap<i32, usize>,
        i: usize,
        j: usize,
        n: usize,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if n <= 0 {
            return None;
        }
        let v = preorder[i];
        let k = d[&v];
        let mut root = TreeNode::new(v);
        root.left = Self::dfs(preorder, d, i + 1, j, k - j);
        root.right = Self::dfs(preorder, d, i + k - j + 1, k + 1, n - k + j - 1);
        Some(Rc::new(RefCell::new(root)))
    }
}