// BINARY TREE :
// Each node can have only 0 1 or at max 2 child.
// Each child can have only one parent.
// So there can be two possible type of tree structure : 1. Perfect Binery Tree 2. Full Binery Tree.
// 1. Perfect Binery tree can have either 0 and 2 child so there will be two benifit if our tree is structure this way
// 1.In each level number of nodes are going to be doubled so at leave one we will have one node then it will have two child so
// at leave two will have two child node then those two will have total four child and this way each level childs node are
// getting doubled so it will be like : 1,2,4,8,16,32 .....
// 2. So because of that structure we can say that 50% of nodes will be as leaf node totalLeafNode = allAboveNodes + 1;
// And because of above structure we are going to see new type type of big o notetion which is O(logn)
// In simple word in this type of notation we don't have to travel entire tree to perform few operation but it traveres based on desitions
// live need to move left or need to move right side.
// Big O for Binery tree : lookeup : O(logn) insert : O(logn) delete : O(logn)
// Understand this O(logn) does not mean half of total items in tree. Giving the example if tree is 10 levels down and if we want to insert
// some values into tree then max decision we need to make is 10 like on each leave only one decision so that means its big o is depend on
// the height of tree or leaves of tree not the total number of nodes in tree.
// (NOTE : ALL ABOVE POINTS WE ARE TALKING ABOUT IS BINERY SEARCH TREE WHERE TREE STRUCTURE IS PERFECT)
// log 100 = 2.
// 10^2 = 100 // We can write both this way
// BINERY SEARCH TREE : 1. It should have 0 1 or 2 nodes.
// 2. All the left node should have less value from there sibling in simple word as tree grows value of the left node on each
// level should be decresed. Like on top if it 100 then all other left node should be 90 , 80 ,45 , 42 .....
// 3. All the right node of the tree should be increse the value as tree grows like if pareant node is 100 then all right side
// node should be 110, 115, 118 .....
// Also this tree makes search very efficient because we don't need to travel enitre tree all it will do is make some decisions and will move to the
// next step accordingly. (GOOD FOR SEARCHING) (ALL OPERATIONS ARE O(logn))
// NOW THERE IS ONE WELL KNOW ISSUE WITH BINERY TREES WHICH IS UNBALANCED BINERY TREE IT MEANS WHAT IF TREE GROWS ONLY IN DIRECTION AND THIS IS
// VERY WELL KNOW PROBLEM AND THERE ARE SOME GOOD SOLUTIONS ALSO AVALIABLE THAT WE WILL DISCUSS LATER ON.
// Best example of unbalanced trees is suppose that you are getting data like this : 10,20,30,40,50,60,70,80,90,100
// Now if we try to create tree as above then all the node will be added on right side and it will look like linked list or like one chain.
// And because of this problem NOW ALL THE OPERATION OF BINERY TREE WILL BECOME O(n) because we need to travers eniter tree to make insert
// update and delete oprations. (This is most asked question is interview also). So for binery trees in worst case big o will be O(n) for all
// operations.
// BINERY TREE implementetion
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor(value){
this.root = null;
this.length = 0;
}
insert(value) {
if(!value) return null;
let newNode = new Node(value);
if(this.root == null){
this.root = newNode;
this.length++;
}else{
let currentNode = this.root;
// WHY DON'T PUT HERE currentNode !== null condition rather then this one
while(true){
if(value > currentNode.value){
if(currentNode.right === null){
currentNode.right = newNode;
this.length++;
return;
}
currentNode = currentNode.right;
}
else{
if(value <= currentNode.value){
if(currentNode.left === null){
currentNode.left = newNode;
this.length++;
return;
}
currentNode = currentNode.left
}
}
}
}
}
getLength(){
return this.length
}
lookup(value){
let currentNode = this.root;
while(currentNode){
if(value > currentNode.value){
currentNode = currentNode.right;
}else if(value < currentNode.value){
currentNode = currentNode.left
}else if(value === currentNode.value){
return currentNode;
}
}
return null
}
// NOTE DONE YET
remove(value){
let currentNode = this.root;
while(currentNode){
if(value > currentNode.value){
currentNode = currentNode.right;
}else if(value < currentNode.value){
currentNode = currentNode.left
}else if(value === currentNode.value){
if(currentNode.left === null && currentNode.right === null){
currentNode = null;
}
}
}
return null
}
traverse(node) {
console.log(node)
const tree = { value: node.value };
tree.left = node.left === null ? null : traverse(node.left);
tree.right = node.right === null ? null : traverse(node.right);
return tree;
}
}
const bst = new BST();
bst.insert(9);
bst.insert(4);
bst.insert(6);
bst.insert(1);
bst.insert(20);
bst.insert(12);
bst.insert(170);
// console.log(bst);
console.log(bst.remove(170))
console.log(bst);
// console.log(bst.getLength())
// There are two type of tree that helps us to make unbalanced tree to balanced and those are AVL TREE AND RED/BLACK tree now those are the most
// used tree and even we are not doing it in this course but once we are done with all this basic concept we must need to do this two tree for sure.
// TWO MORE TYPES OF TREE : (Need to learn lot about trees after done with this basic stuff) 1. BINARY HEAP 2.TRIE
// Binery Heaps : in this each parent value will be higher then it left and right child.
// But here its not mandetory this left should have small value and right should have large value like BST.
// Also we can create two types of Binary Heaps tree one in which root node will have min value and one in
// which root node will have max value. Above example was for max root value so all the child will have small value then root.
// but in other case if root is min then all other child value should be large then root value. AND MAKE SURE IT DOES NOT ONLY
// aplies to only root not but each leave parent.
// MAILY USED IN PRIORITY QUEUE that we will learn
// BIG O : insert : O(logn) lookup : O(n) and delete : O(logn)
// Also will will do binery heap with help of visual algo as those are not as hard as AVL AND BLACK RED tree.
