Inverting A Binary Tree in JavaScript and Python
Tags: binary, javascript, python, tutorial
Published: 2021-03-13 08:32:34

Famously the creator of Homebrew failed a google interview because he failed to invert a binary tree on a whiteboard. Let's go through implementing it. Inverting a binary tree involves switching non-leaf nodes on the left side with the ones on the Right.
The image below shows a brief representation of the process.
![Invert tree](https://www.techiedelight.com/wp-content/uploads/invert-binary-tree.png).

The steps to follow:-
1. store the left property to the node
2. set the left property to the right property of the node
3  set the right property to the stored left property 
4. recursively call InvertBinary on the left property of the 
   node then on the right property of the node.
5. return the tree.

Code implementation in JavaScript:-
```js
class Node{
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST{
    constructor(){
        this.root = null;
    }

    insert(val){
        let newNode = new Node(val);
        if(!this.root){
            this.root = newNode;
        }else{
            let current = this.root;
            while(true){
                if(val < current.val){
                    if(current.left === null){
                        current.left = newNode;
                        return this
                    }else{
                        current = current.left;
                    }
                }else{
                    if(current.right === null){
                        current.right = newNode;
                        return this
                    }else{
                        current = current.right
                    }
                }
            }

        }

    }

       DFSInOrder(){
        let data=[];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.val);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;

    }

    IBT(){
        function Invert(node){
            if(node === null) return ;
            let temp = node.left;
            node.left = node.right;
            node.right = temp;

            Invert(node.left);
            Invert(node.right);
        }
        Invert(this.root)
        return this.DFSInOrder()
    }



}

let tree = new BST();
tree.insert(100);
tree.insert(200);
tree.insert(150);
tree.insert(80);
tree.insert(90);
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(180);
tree.insert(190);
tree.DFSInOrder();
tree.IBT();
```


in Python:-
```py
class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        
        
class BST:
    def __init__(self):
        self.root= None
        
    def insert(self, val):
         newNode = Node(val)
         if self.root == None:
             self.root= newNode
         else:
             current = self.root
             while True:
                 if val< current.val:
                     if current.left == None:
                         current.left = newNode
                         return self
                     else:
                         current= current.left 
                 else:
                     if(current.right == None):
                         current.right = newNode
                         return self
                     else:
                         current = current.right
                           
    
    def dfsInorder(self):
        data =[]
        
        def traverse(node):
            if(node.left): traverse(node.left)
            data.append(node.val)
            if(node.right): traverse(node.right)
        traverse(self.root)         
        return data
    
    
    
    
    def IBT(self):
        def InvertTree(node):
            if node == None: return 
            
            temp= node.left
            node.left = node.right
            node.right = temp
            
            InvertTree(node.left)
            InvertTree(node.right)
        InvertTree(self.root) 
            
        return self.dfsInorder()
        
bst = BST()
bst.insert(100)
bst.insert(200)
bst.insert(150)
bst.insert(175)
bst.insert(160)
bst.insert(180)
bst.insert(75)
bst.insert(50)
bst.insert(65)
bst.insert(40)
bst.insert(55)
bst.insert(20)

print(bst.dfsInorder())
print(bst.IBT())

```


Have a nice weekend.