LiquidAI/LFM2-24B-A2B-GGUF:Q4_K_M: "Invert a binary tree in JS and print an ascii representation of the before and after"

binary-tree.md

To invert a binary tree in JavaScript and display an ASCII representation of the tree before and after the inversion, follow these steps:

Approach

1. Define a Tree Node Class: Create a class to represent each node of the binary tree, containing val, left, and right properties.
2. Invert the Binary Tree: Use a recursive approach to swap the left and right children of each node. This is done by traversing the tree and swapping the children of each node.
3. Generate ASCII Tree Representation: Implement a function to convert the tree into a string representation that visually shows the structure, including node values and their positions. This function uses level-order traversal (breadth-first search) to handle varying node depths and spaces.
4. Display Results: Print the original and inverted tree's ASCII representations.

Solution Code

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

// Function to invert the binary tree
function invertTree(root) {
    if (root === null) return null;
    // Swap left and right children
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
    return root;
}

// Helper function to generate a string representation of the tree
function treeToString(root) {
    if (root === null) return '';
    const queue = [root];
    let result = '';
    let level = 0;
    while (queue.length > 0) {
        const levelSize = queue.length;
        let currentLevel = '';
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel += `${node.val}`;
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        // Add spaces after each node except the last to avoid trailing spaces
        if (currentLevel.length > 0) {
            currentLevel += ' '.repeat(level * 2);
            if (level < 2) {
                currentLevel += '| ';
            } else {
                currentLevel += '';
            }
        }
        // Add separator between levels (except after last level)
        result += currentLevel + (level < 2 ? '  ' : '') + '\n';
        level++;
    }
    // Trim the last newline and return the string
    return result.trim();
}

// Example usage
// Create a sample binary tree (original structure)
const originalRoot = new TreeNode(1, 
    new TreeNode(2, 
        new TreeNode(4), 
        new TreeNode(5)
    ), 
    new TreeNode(3, 
        new TreeNode(7), 
        new TreeNode(6)
    )
);

console.log("Original Tree ASCII Representation:");
console.log(treeToString(originalRoot));

// Invert the tree
const invertedRoot = invertTree(originalRoot);

console.log("Inverted Tree ASCII Representation:");
console.log(treeToString(invertedRoot));

Explanation

• TreeNode Class: Represents each node with a value and pointers to left and right children.
• invertTree Function: Recursively swaps the left and right children of each node, effectively inverting the tree.
• treeToString Function: Uses level-order traversal to generate a string. Each level is processed by dequeuing nodes, collecting their values, and enqueuing their children. Spaces and separators are added to visually represent the tree structure.
• Example Usage: Demonstrates creating a tree, inverting it, and displaying both the original and inverted ASCII representations.

This approach ensures the tree is inverted correctly and visually represented in a readable format.