Trees

// 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;
// }
}