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)