// level 0 : 2^0 = 1
// level 1 : 2^1 = 2
// level 2 : 2^2 = 4
// level 3 : 2^3 = 8
// # of nodes = 2^h -1
// log nodes = height
// log 100 = 2
//10^2 = 1
class Node {
dynamic left;
dynamic right;
dynamic value;
Node(value) {
this.left = null;
this.right = null;
this.value = value;
}
Map<String, dynamic> toMap(){
return {
"value": value,
"left": left?.toMap(),
"right": right?.toMap()
};
}
}
class BinarySearchTree {
dynamic root;
BinarySearchTree() {
this.root = null;
}
Map<String, dynamic> toMap(){
return root?.toMap() ?? {};
}
insert(value) {
Node newNode = new Node(value);
if(root == null){
// Node.value = value;
root = newNode;
}else{
dynamic tree = traverse(root, newNode.value);
if(value > tree.value){
// print(tree.toString());
tree.right = newNode;
}else{
// print(tree.toString());
tree.left = newNode;
}
}
}
lookup(value) {
dynamic node = this.root;
while(true){
if(value < node.value){
if(node.left == null){
return null;
}
node = node.left ;
}else if(value == node.value){
return node.value;
}else {
if(node.right == null){
return null;
}
node = node.right;
}
}
}
remove(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while (currentNode) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if (currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if (parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if (currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while (leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if (parentNode === null) {
this.root = leftmost;
} else {
if (currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if (currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
traverse(node, value) {
dynamic tree = node;
while(true){
if(value < tree.value){
if(tree.left == null) return tree;
tree = tree.left;
}else{
if(tree.right == null )return tree;
tree = node.right;
}
}
return tree;
}
@override
String toString(){
return toMap().toString();
}
}
void main(){
BinarySearchTree tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
tree.remove(4);
print(tree.lookup(171));
// JSON.stringify(traverse(tree.root));
print(tree);
// 9
// 4 20
//1 6 15 170
// function traverse(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;
// }
}
