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) {
    
};

[root.left, root.right] = [root.right, root.left] then do same for children — Photon
– Photon, Commented Jul 17, 2020 at 13:06
Simply swap left node with right node, try my binary tree class which comes with build it function reverse(). Refer links - Class - npmjs.com/package/@dsinjs/binary-tree Documentation - dsinjs.github.io/binary-tree/#reverse — Siddhesh Kulkarni
– Siddhesh Kulkarni, Commented Nov 29, 2020 at 19:30

EugenSunic · Accepted Answer · 2022-02-28 12:56:06Z

9

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

edited Feb 28, 2022 at 12:56

EugenSunic

13.8k15 gold badges68 silver badges96 bronze badges

answered Nov 29, 2020 at 19:53

Siddhesh Kulkarni

3584 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tkane2000 Over a year ago

Seems like it would be more clear to swap the values after you traverse rather than before.

Nick Parsons · Accepted Answer · 2020-07-17 13:52:26Z

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));

Richie Bendall · Accepted Answer · 2021-03-19 23:58:19Z

1

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)]
}

answered Mar 19, 2021 at 23:58

Richie Bendall

9,4444 gold badges51 silver badges66 bronze badges

2 Comments

php_nub_qq Over a year ago

1 up for 1 liners.

luhfluh Over a year ago

this would work for only Fully Balanced Binary Tree. Not for any Binary Tree

Scott Sauyet · Accepted Answer · 2022-02-28 15:06:56Z

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}

Eme · Accepted Answer · 2022-07-05 19:44:48Z

0

function invertTree(node) {
    if (node && node.left) {
        let left = node.left;
        node.left = node.right;
        node.right = left;
        invertTree(node.right);
        invertTree(node.left);
    }
    return node;
}

const n = {value: 5, left: {left: 5, right: 6 }, right: {left: 1, right: 2}};
console.log(invertTree(n))

answered Jul 5, 2022 at 19:44

Eme

811 silver badge5 bronze badges

Comments

Avazkhon · Accepted Answer · 2021-12-05 08:21:04Z

-1

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))

answered Dec 5, 2021 at 8:21

Avazkhon

1

Collectives™ on Stack Overflow

How can I invert a binary tree in JavaScript?

6 Answers 6

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related