Subtree of Another Tree - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const VALUE_MATCH = 'value_match', VALUE_MATCH_COLOR = 'lightgreen';
const MATCH = 'match', MATCH_COLOR = 'green';
const MISMATCH = 'mismatch', MISMATCH_COLOR = 'red';

function visMainFunction(mainInput, subInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const mainRoot = convertInputToTree(mainInput);
    const subRoot = convertInputToTree(subInput);

    startBatch();
    const mainTree = new VisBinaryTree(mainRoot, { dataPropName: 'val' }); 
    const subTree = new VisBinaryTree(subRoot, { dataPropName: 'val' }); 
    endBatch();

    const result = isSubtree(mainRoot, subRoot, mainTree, subTree);
    
    if (result) {
        notification(`✅ The <b>subTree (subRoot)</b> <b>is</b> a subtree of the <b>mainTree (root)</b>.`);
    } else {
        notification(`❌ The <b>subTree (subRoot)</b> <b>is not</b> a subtree of the <b>mainTree (root)</b>.`);
    }

    return result;
}

// Note that the parameters coming after subroot are not part of the original algorithm but they are included to be used in visualization
function isSubtree(root, subRoot, mainTree, subTree) {
    if (!root) return false;

    startPartialBatch();
    setCurrentNode(root, mainTree);
    notification(`
        🔵 Checking whether the <b>subTree (subRoot)</b>  
        could be a <b>subtree of</b> the ${makeColoredSpan('current main-tree node', CURRENT_COLOR)}.<br>
        We’ll now test if they represent the <b>same tree</b> — meaning they share the <b>same structure</b> and <b>node values</b>.<br>
        If they match, return <code>true</code>; otherwise, recursively repeat this check for the  
        <b>descendants</b> of the ${makeColoredSpan('current main-tree node', CURRENT_COLOR)}.
    `);
    endBatch();

    if (isSameTree(root, subRoot, mainTree, subTree)) {
        return true;
    }

    const [leftPrecall, rightPrecall] = postIsSubtree(root, subRoot, mainTree, subTree);
    return isSubtree(root.left, subRoot, mainTree, subTree, leftPrecall) || isSubtree(root.right, subRoot, mainTree, subTree, message, rightPrecall);
}

// Note that the parameters coming after b are not part of the original algorithm but they are included to be used in visualization
function isSameTree(a, b, treeA, treeB, precall) {
    precall && precall(); 
    if (!a && !b) return true;

    startPartialBatch();
    setCurrentNode(a, treeA);
    setCurrentNode(b, treeB);
    notification(`
        🔵 Comparing the ${makeColoredSpan('current nodes', CURRENT_COLOR)}  
        of both trees to determine if they represent the <b>same tree</b> — meaning they share the <b>same structure</b> and <b>node values</b>.<br>
        We first compare their <b>values</b>; if they differ, return <code>false</code> immediately.<br>
        If the values match, we recursively compare their <b>left</b> and <b>right</b> subtrees.<br>
        In the <b>base case</b>, when both nodes are <code>null</code>, we return <code>true</code>.
    `);

    if (!a || !b || a.val !== b.val) { 
        handleMismatch(a, b, treeA, treeB);
        endBatch();
        return false;
    }

     const [handleLeftMatch, handleMatch] = handleValueMatch(a, b, treeA, treeB);
     endBatch();

    return isSameTree(a.left, b.left, treeA, treeB) && handleLeftMatch() && isSameTree(a.right, b.right, treeA, treeB) && handleMatch(); 
}

// --- Helpers ---

let treeToCurentNode = new Map();

function setCurrentNode(node, tree) { 
    const lastNode = treeToCurentNode.get(tree);
    if (lastNode === node) return;
    startBatch();
    lastNode && tree.makeVisManagerForNode(lastNode).removeClass(CURRENT); 
    node && tree.makeVisManagerForNode(node).addClass(CURRENT);
    treeToCurentNode.set(tree, node);
    endBatch();
    return true;
} 

function postIsSubtree(root, subRoot, mainTree, subTree) {
    clearHighlightsBatched(root, subRoot, mainTree, subTree);
    const leftPrecall = () => { 
        setCurrentNode(root, mainTree); 
        notification(`
            🔵 The ${makeColoredSpan('current main-tree node', CURRENT_COLOR)}  
            did not match the subtree structure or values.  
            Moving to its <b>left subtree</b> to continue the search.
        `); 
    };
    const rightPrecall = () => { 
        setCurrentNode(root, mainTree);  
        notification(`
            🔵 No match found in the ${makeColoredSpan('current main-tree node', CURRENT_COLOR)}  
            or its <b>left subtree</b>.  
            Proceeding to check its <b>right subtree</b> for a possible match.
        `);
    };

    return [leftPrecall, rightPrecall];
}

function handleValueMatch(a, b, treeA, treeB) {
    const vmA = treeA.makeVisManagerForNode(a);
    const vmB = treeB.makeVisManagerForNode(b);

    startPartialBatch();
    vmA.addClass(VALUE_MATCH);
    vmB.addClass(VALUE_MATCH);
    notification(`🟢 Values match for the ${makeColoredSpan('current nodes', CURRENT_COLOR)}. Proceeding to compare their <b>left subtrees</b> next.`);
    endBatch();

    const handleLeftMatch = () => {
        startPartialBatch();
        setCurrentNode(a, treeA);
        setCurrentNode(b, treeB);
        notification(`🟢 Both values and <b>left subtrees</b> match for the ${makeColoredSpan('current nodes', CURRENT_COLOR)}. Proceeding to compare their <b>right subtrees</b> next.`);
        endBatch();
        return true;
    };

    const handleMatch = () => {
        startPartialBatch();
        setCurrentNode(a, treeA);
        setCurrentNode(b, treeB);
        notification(
            `✅ <b>Subtrees match</b> at the ${makeColoredSpan('current nodes', CURRENT_COLOR)}. 
            Both <b>values</b> and <b>structures</b> are identical — confirming they represent the <b>same tree</b>.
        `);
        vmA.removeClass(VALUE_MATCH).addClass(MATCH);
        vmB.removeClass(VALUE_MATCH).addClass(MATCH);
        endBatch();
        return true;
    }

    return [handleLeftMatch, handleMatch];
}
 
function handleMismatch(a, b, treeA, treeB) {
    const message = (!a || !b)
        ? `❌ <b>Structure mismatch</b> — one node is <code>null</code> while the other is not.`
        : `❌ <b>Value mismatch</b>: <code>${a.val}</code> ≠ <code>${b.val}</code>.`;
    a && treeA.makeVisManagerForNode(a).addClass(MISMATCH);
    b && treeB.makeVisManagerForNode(b).addClass(MISMATCH);
    notification(message);
}

function clearHighlightsBatched(root, subRoot, mainTree, subTree) {
    startBatch();
    clearHighlights(root, subRoot, mainTree, subTree);
    treeToCurentNode = new Map();
    endBatch();
}

function clearHighlights(root, subRoot, mainTree, subTree) {
    root && mainTree.makeVisManagerForNode(root).removeAllClasses();
    subRoot && subTree.makeVisManagerForNode(subRoot).removeAllClasses();
    
    if (!root || !subRoot || root.val !== subRoot.val) {
        return;
    }

    clearHighlights(root.left, subRoot.left, mainTree, subTree);
    clearHighlights(root.right, subRoot.right, mainTree, subTree);
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(MATCH, { backgroundColor: MATCH_COLOR });
    setClassProperties(MISMATCH, { backgroundColor: MISMATCH_COLOR });
    setClassProperties(VALUE_MATCH, { backgroundColor: VALUE_MATCH_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val))); 
    for (let i = 0; i < nodes.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

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

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    <b>🎨 Visual Cues (Color Schema)</b>
    <ul>
      <li>${makeColoredSpan('Current node (main/sub)', CURRENT_COLOR)} — ${CURRENT_COLOR} border while a pair of nodes is being compared.</li>
      <li>${makeColoredSpan('Value match', VALUE_MATCH_COLOR)} — ${VALUE_MATCH_COLOR} background after values are equal (before/full-structure checks continue).</li>
      <li>${makeColoredSpan('Confirmed identical subtree', MATCH_COLOR)} — ${MATCH_COLOR} background when both value and structure match for the compared subtrees.</li>
      <li>${makeColoredSpan('Mismatch', MISMATCH_COLOR)} — ${MISMATCH_COLOR} background when either structure differs or values are not equal (including one null, one non-null).</li>
    </ul>
  `);
}

Approach

The recursion starts from the root (main tree) and explores every node to check whether the subTree (subRoot) is identical to any subtree within it. We do this using the main recursive function isSubtree(root, subRoot), which traverses the main tree, and a helper isSameTree(a, b) that checks if two trees are identical.

isSubtree(root, subRoot):
This function both traverses the main tree and triggers comparison at each node.
- If root is null, return false — we've reached the end without a match.
- Check if isSameTree(root, subRoot) returns true — if yes, we found a subtree match.
- If not, recursively call isSubtree(root.left, subRoot) and isSubtree(root.right, subRoot).
During this recursion, the main-tree root changes at each step, while the subTree (subRoot) stays constant — since we are trying to find where it matches inside the main tree.
isSameTree(a, b):
Checks if two trees are identical in structure and node values.
- If both null → true (structures align at leaves).
- If only one is null → false (structure mismatch).
- If a.val !== b.val → false (value mismatch).
- Otherwise → recursively check isSameTree(a.left, b.left) and isSameTree(a.right, b.right).

💡 Why this works

The isSubtree recursion ensures every possible node in the main tree is tested as a potential root for the subtree. The helper isSameTree ensures that a match is only confirmed if both structure and values align perfectly from that point downward.

Time Complexity

O(N × M) — for each of the N nodes in the main tree, we may compare up to M nodes in the subtree during isSameTree checks.

Space Complexity

O(H_N + H_M) auxiliary space — caused by the recursion depth, where H_N and H_M are the heights of the main and sub trees, and N and M are their respective node counts. In the worst case (skewed trees), heights become equal to their sizes.

Input-1

Subtree of Another Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

💡 Why this works

Time Complexity

Space Complexity