How can I invert a binary tree in JavaScript?

Question

how can i flip over binary tree? I recently came across this problem, and all my attempts to do it adequately failed. initial tree shown below.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    
};

Answer 1

It will be easier with recursive method in js using DFS (depth first search) and simply swap the nodes

    const trav = (currNode) => {
      if (currNode === null) {
        return;
      }
      const temp = currNode.lNode;
      currNode.lNode = currNode.rNode;
      currNode.rNode = temp;
      trav(currNode.lNode);
      trav(currNode.rNode);
    };
    trav(root);
    return root;

For more refer to the class I wrote for more interesting methods -
Class - https://www.npmjs.com/package/@dsinjs/binary-tree
Documentation for reverse() method - https://dsinjs.github.io/binary-tree/#reverse

Answer 2

For every node with at least one child, you can swap its children by making the node's .left value equal to the node's .right value, and the node's .right value equal to the (old) .left value. Once you've swapped the children, you can then see whether you have to do the same process for the subtrees rooted at the children nodes by recursively calling your invertTree() function. If a node doesn't have either left or right children, then you're at a leaf, meaning you can return the passed in node (as no further child swapping is required).

function Node(val, left, right) {
  this.val = (val===undefined ? 0 : val);
  this.left = (left===undefined ? null : left);
  this.right = (right===undefined ? null : right);
}

const invertTree = function(root) {
  if(!root || !root.left && !root.right) { // base case
    return root;
  }
  
  const oldLeft = root.left;
  root.left = root.right;
  root.right = oldLeft;
  invertTree(root.left);
  invertTree(root.right);
  return root;
};


const tree = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(7, new Node(6), new Node(9)));
console.log(invertTree(tree));

Answer 3

You can just recurse through the tree, mutating it with the left and right sides swapped if they exist.

const invertTree = tree => {
    if (!(tree?.left && tree?.right)) {
        return tree
    }

    [tree.right, tree.left] = [invertTree(tree.left), invertTree(tree.right)]
}

Answer 4

A recent edit to an answer bubbled this older question to the top, and I didn't see any simple answer that treated the data immutably. So here is one quick function:

const invertTree = (t) =>
  t === null ? null : new TreeNode (t .val, invertTree (t .right), invertTree (t .left))

const tree = new TreeNode (4, new TreeNode (2, new TreeNode (1), new TreeNode (3)), new TreeNode (7, new TreeNode (6), new TreeNode (9)))

const inverted = invertTree (tree)

// Note that the original is not mutated:
console .log ('Original: ', JSON .stringify (tree, null, 4))
console .log ('Inverted: ', JSON .stringify (inverted, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

<script>function TreeNode (val, left, right) {this .val = (val === undefined ? 0 : val); this .left = (left === undefined ? null : left); this .right = (right === undefined ? null : right)}</script>

In our base case, the node is null and we return null. Otherwise we construct a new node with the same val, and with recursive calls to invertTree passing the right node and the left node in that order so that the new tree has them swapped.

If it were up to me, I would not use a constructor function (nor a class) for this but a simple data constructor:

const node = (val, left, right) => ({val, left: left || null, right: right || null})

const invertTree = (t) =>
  t == null ? null : node (t .val, invertTree (t .right), invertTree (t .left))

const tree = node (4, node (2, node (1), node (3)), node (7, node (6), node (9)))
const inverted = invertTree (tree)

console .log ('Original: ', JSON .stringify (tree, null, 4))
console .log ('Inverted: ', JSON .stringify (inverted, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

Answer 5

I solved this problem like this. Try this algorithm. I know it's late, but it will help others

 const node = {
    value: 1,
    left: {
      value: 2,
      left: { value: 4  },
       right: { value: 5  }   
    },
    right: {
       value: 3,
       left: { value: 6},
       right: { value: 7  }
    }
 }

invertFree = (node) => {
    if (node) {
        const newNode = { value: node.value }
        if (node.right) {
            newNode.left = invertFree(node.right)
        }
        if (node.left) {
           newNode.right = invertFree(node.left)
        }
        return newNode
    }
}

console.log(invertFree(node))