Invert Binary 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 INVERTED = 'inverted', INVERTED_COLOR = 'green';
const IN_PROGRESS = 'in_progress', IN_PROGRESS_COLOR = 'gray';

function visMainFunction(treeInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const root = convertInputToTree(treeInput);
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });

    invertTree(root, tree);
    notification(`🏁 <b>Done!</b> The binary tree has been successfully inverted.`);
    return root;
}

function invertTree(node, tree) {
    if (!node) {
        notification(`🌿 Encountered a <code>null</code> node — this marks an empty branch, so there’s nothing to invert.`);
        return null;
    }

    startPartialBatch();
    setAsCurrentNode(node, tree);
    notification(`⏳ Starting inversion for the ${makeColoredSpan('current node', CURRENT_COLOR)} — marking it as ${makeColoredSpan('in progress', IN_PROGRESS_COLOR)} and beginning with its left subtree.`);
    tree.makeVisManagerForNode(node).addClass(IN_PROGRESS);
    endBatch();

    // Recurse left
    const left = invertTree(node.left, tree);
    startPartialBatch();
    setAsCurrentNode(node, tree);
    notification(`✅ Finished inverting the left subtree of the ${makeColoredSpan('current node', CURRENT_COLOR)}. Now moving on to the right subtree.`);
    endBatch();

    // Recurse right
    invertTree(node.right, tree);
    startPartialBatch();
    setAsCurrentNode(node, tree);
    notification(`✅ Both subtrees of the ${makeColoredSpan('current node', CURRENT_COLOR)} are inverted. ↔️ Performing the final step — swapping its left and right children to complete its inversion.`);

    tree.preserveNode(left); 
    node.left = node.right;
    node.right = left;
    tree.undoPreserveNode(left);
    
    tree.makeVisManagerForNode(node).removeClass(IN_PROGRESS).addClass(INVERTED);
    notification(`🎉 Swap complete! The ${makeColoredSpan('current node', CURRENT_COLOR)} is now fully ${makeColoredSpan('inverted', INVERTED_COLOR)}.`);
    endBatch();
    return node;
}

let current = null;

function setAsCurrentNode(node, tree) {
    startBatch();
    if (current) {
        tree.makeVisManagerForNode(current).removeClass(CURRENT);
    }
    tree.makeVisManagerForNode(node).addClass(CURRENT);
    current = node;
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(INVERTED, { backgroundColor: INVERTED_COLOR });
    setClassProperties(IN_PROGRESS, { backgroundColor: IN_PROGRESS_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 < arr.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:</b>
    <ul>
        <li>${makeColoredSpan(CURRENT_COLOR + ' border', CURRENT_COLOR)} → marks the <b>current node</b> being processed.</li>
        <li>${makeColoredSpan(IN_PROGRESS_COLOR + ' background', IN_PROGRESS_COLOR)} → indicates a node whose inversion is in progress.</li>
        <li>${makeColoredSpan(INVERTED_COLOR + ' background', INVERTED_COLOR)} → marks a node whose inversion is completed.</li>
    </ul>
    `);
}

Approach

We invert the binary tree using a post-order DFS traversal — process the left subtree first, then the right subtree, and finally swap the two child pointers of the current node to complete its inversion. This ensures that before the swap occurs, both of the node’s subtrees have already been inverted.

Base case: If the node is null, it indicates an empty branch — return null immediately since there’s nothing to invert.
Recursive step (post-order):
1. Recursively invert the left subtree.
2. Recursively invert the right subtree.
3. Swap node.left and node.right after both subtrees have been processed.
4. Return the current node.

Time Complexity

O(n), where n is the number of nodes — each node is visited exactly once.

Space Complexity

O(h), where h is the height of the tree — recursion stack proportional to the tree height (O(n) in the worst case for a skewed tree; O(log n) for a balanced tree).

Input-1

Invert Binary Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity