Construct Binary Tree from Preorder and Inorder Traversal - JS Solution

Solution code

const PREORDER_INDEX = 'preorder_index', PREORDER_INDEX_COLOR = 'gold';
const LEFT = 'left', LEFT_COLOR = 'blue';
const RIGHT = 'right', RIGHT_COLOR = 'orange';
const ROOT_IDX = 'root_idx', ROOT_IDX_COLOR = 'gold';
const CURRENT_TREE = 'current_tree', CURRENT_TREE_COLOR = 'gray';

function visMainFunction(preorderInput, inorderInput) {  
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const preorder = new VisArray(...preorderInput);
    const inorder = new VisArray(...inorderInput);

    const inorderIndexMap = new VisMap();
    inorder.forEach((val, idx) => inorderIndexMap.set(val, idx));

    let preorderIndex = 0;
    makeVisVariable(preorderIndex).registerAsIndexPointer(preorder, PREORDER_INDEX);

    let leftPointer, rightPointer, rootIndexPointer;
    makeVisVariable(leftPointer).registerAsIndexPointer(inorder, LEFT); 
    makeVisVariable(rightPointer).registerAsIndexPointer(inorder, RIGHT);
    makeVisVariable(rootIndexPointer).registerAsIndexPointer(inorder, ROOT_IDX);
    endBatch();

    notification(`
        🗺️ Before starting recursion, we initialize two key helpers:
        <ul>
        <li><code>inorderIndexMap</code> — maps each value in <code>inorder</code> to its index.  
            This gives <b>O(1)</b> access when locating a root’s position to split into left and right subtrees,  
            avoiding repeated scans of the array.</li>
        <li><code>preorderIndex</code> — initialized to <b>0</b> and registered as a moving pointer over <code>preorder</code>.  
            It always points to the next node that should become a <b>root</b> in the reconstruction process.</li>
        </ul>
        🚀 With these ready, we call <code>buildTreeHelper(0, ${inorderInput.length - 1})</code>  
        to begin constructing the full tree from the <b>entire inorder range</b>.
    `);

    function buildTreeHelper(left, right, path='~') {
        startPartialBatch();
        rootIndexPointer = undefined; leftPointer = left; rightPointer = right; 
        notification(`
            🧩 <b>Building subtree</b> for path "<b>${path}</b>": Considering <b>inorder indices</b>  from ${makeColoredSpan('left', LEFT_COLOR)} <b>${left}</b>  
            to ${makeColoredSpan('right', RIGHT_COLOR)} <b>${right}</b>. This range defines the portion of the array that belongs to the <b>current subtree</b>.
        `);

        if (left > right) {
            notification(`
                🔚 Base case reached — ${makeColoredSpan('left', LEFT_COLOR)} > ${makeColoredSpan('right', RIGHT_COLOR)}. This means there are <b>no nodes</b> to place in this range,  
                so we return <code>null</code> to indicate an <b>empty subtree</b>.
            `);
            endBatch();
            return null;
        }

        const rootVal = preorder[preorderIndex];
        notification(`
            🌱 <b>Selecting root:</b> The value at the current ${makeColoredSpan('preorderIndex', PREORDER_INDEX_COLOR)} is <b>${rootVal}</b>.  
            Because <b>preorder traversal lists roots first</b>, this element becomes the <b>root of the current subtree</b>.  
            We then advance ${makeColoredSpan('preorderIndex', PREORDER_INDEX_COLOR)} to prepare for the next subtree.
        `);

        preorderIndex += 1;
        const root = new TreeNode(rootVal);
        const tree = new VisBinaryTree(root, { dataPropName: 'val' }).options({ label: path });
        setCurrentTree(tree);

        const rootIdx = inorderIndexMap.get(rootVal);
        rootIndexPointer = rootIdx;
        notification(`
            📍 Looked up <code>inorderIndexMap</code> and found that <b>${rootVal}</b>  
            is located at ${makeColoredSpan('rootIdx', ROOT_IDX_COLOR)} <b>${rootIdx}</b> in the <code>inorder</code> array.  
            All elements <b>to the left</b> of this ${makeColoredSpan('rootIdx', ROOT_IDX_COLOR)} form the <b>left subtree</b>,  and all elements <b>to the right</b> of it form the <b>right subtree</b>.  
            🏗️ Now building and assigning the <b>left subtree</b>, covering the index range from ${makeColoredSpan('left', LEFT_COLOR)} (<b>${left}</b>) to ${makeColoredSpan('rootIdx − 1', ROOT_IDX_COLOR)} (<b>${rootIdx - 1}</b>).
        `);
        endBatch();
        
        root.left = buildTreeHelper(left, rootIdx - 1, expandPath(path, 'L')); 

        startPartialBatch();
        setCurrentTree(tree);
        leftPointer = left; rightPointer = right; rootIndexPointer = rootIdx;
        notification(`
            ⬅️ Assigned the <b>left subtree</b> for path "<b>${path}</b>", whose root value <b>${makeColoredSpan(rootVal, ROOT_IDX_COLOR)}</b> is located at ${makeColoredSpan('rootIdx', ROOT_IDX_COLOR)} <b>${rootIdx}</b> 
            in the <code>inorder</code> array. Now proceeding to build and assign the <b>right subtree</b> — covering the inorder index range from  
            ${makeColoredSpan('rootIdx + 1', ROOT_IDX_COLOR)} (<b>${rootIdx + 1}</b>) to ${makeColoredSpan('right', RIGHT_COLOR)} (<b>${right}</b>).
        `);
        endBatch();

        root.right = buildTreeHelper(rootIdx + 1, right, expandPath(path, 'R')); 
 
        startPartialBatch();
        setCurrentTree(tree);
        leftPointer = left; rightPointer = right; rootIndexPointer = rootIdx;
        notification(`✅ Completed the <b>subtree</b> for path "<b>${path}</b>", with root value <b>${rootVal}</b>. All recursive branches for this subtree are now built and connected.`); 
        tree.destroyVis();
        endBatch();

        return root; 
    }

    const root = buildTreeHelper(0, inorderInput.length - 1);
    notification(`🏁 <b>Tree reconstruction complete.</b>`);
    return root;
}

let currentTree;

function setCurrentTree(tree) {
    if (tree === currentTree) return; 
    startBatch();
    currentTree?.visManager.removeClass(CURRENT_TREE);
    tree?.visManager.addClass(CURRENT_TREE);
    currentTree = tree;
    endBatch();
}

function expandPath(path, direction) {
    return path + '.' + direction;
}

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

function initClassProperties() {
    setClassProperties(PREORDER_INDEX, { backgroundColor: PREORDER_INDEX_COLOR });
    setClassProperties(LEFT, { borderColor: LEFT_COLOR });
    setClassProperties(RIGHT, { borderColor: RIGHT_COLOR });
    setClassProperties(ROOT_IDX, { backgroundColor: ROOT_IDX_COLOR }); 
    setClassProperties(CURRENT_TREE, { backgroundColor: CURRENT_TREE_COLOR });
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues (Color Schema)</b>
        <ul>
            <li>${makeColoredSpan('Preorder index pointer', PREORDER_INDEX_COLOR)} — highlighted with a <b>${PREORDER_INDEX_COLOR} background</b> to mark the <b>current root</b> being processed in <code>preorder</code>.</li>
            <li>${makeColoredSpan('Left bound', LEFT_COLOR)} — highlighted with a <b>${LEFT_COLOR} border</b> to show the <b>left limit</b> of the current <code>inorder</code> segment.</li>
            <li>${makeColoredSpan('Right bound', RIGHT_COLOR)} — highlighted with a <b>${RIGHT_COLOR} border</b> to show the <b>right limit</b> of the current <code>inorder</code> segment.</li>
            <li>${makeColoredSpan('Root index (rootIdx)', ROOT_IDX_COLOR)} — highlighted with a <b>${ROOT_IDX_COLOR} background</b> to indicate the <b>position of the current root</b> in the <code>inorder</code> array, where the split occurs.</li>
            <li>${makeColoredSpan('Current subtree', CURRENT_TREE_COLOR)} — highlighted with a <b>${CURRENT_TREE_COLOR} background</b> to emphasize the <b>subtree currently being built</b> during recursion.</li>
        </ul>
    `);
}