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.
.
The steps to follow:-
- store the left property to the node
- set the left property to the right property of the node 3 set the right property to the stored left property
- recursively call InvertBinary on the left property of the node then on the right property of the node.
- 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();
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())
Have a nice weekend.
Top comments (0)