DEV Community

Edwin
Edwin

Posted on

3 2

Inverting A Binary Tree in JavaScript and Python

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.

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
  3. recursively call InvertBinary on the left property of the node then on the right property of the node.
  4. return the tree.

Code implementation in JavaScript:-

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();
Enter fullscreen mode Exit fullscreen mode

in Python:-

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

Enter fullscreen mode Exit fullscreen mode

Have a nice weekend.

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay