BFS/DFS

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




  
 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;
}
 // iterative 
 breathFirstSearch(){
        var currentNode = root;
        var  list = [];
        var queue = [];
        queue.add(currentNode);
      
        while(queue.length > 0){
           print(currentNode.value);
            currentNode = queue.removeAt(0); //when you remove from queue here the queue becomes empty again at initial stage 
            list.add(currentNode.value);
            if(currentNode.left != null){
                queue.add(currentNode.left);
            }
            if(currentNode.right != null){
                queue.add(currentNode.right);
            }
            
        }
        
        return list;
    }
    
 // recursive
  breathFirstSearchR(queue, list){
      if(queue.length == 0){
          return list;
      }
     
        var currentNode = queue.removeAt(0); //when you remove from queue here the queue becomes empty again at initial stage 
        list.add(currentNode.value);
        if(currentNode.left != null){
            queue.add(currentNode.left);
        }
        if(currentNode.right != null){
            queue.add(currentNode.right);
        }
        return breathFirstSearchR(queue, list);
  }
  
  DFSInOrder(root, list){
      return traverseInOrder(root,list);
  }
   DFSPreOrder(root, list){
      return traversePreOrder(root,list);
  }
   DFSPostOrder(root, list){
      return traversePostOrder(root,list);
  }
  
  traverseInOrder(node, list){
      if(node.left != null){
          traverseInOrder(node.left,list);
      }
      list.add(node.value); // this first adds the left nodes values to the list before the right
      
      if(node.right != null){
          traverseInOrder(node.right,list);
      }
      return list;
  }
  
   traversePreOrder(node, list){
      list.add(node.value);  // this first adds the first nodes values to the list before the left before the right
      if(node.left != null){
          traversePreOrder(node.left,list);
      }
   
      
      if(node.right != null){
          traversePreOrder(node.right,list);
      }
      return list;
  }
  
    traversePostOrder(node, list){
      
      if(node.left != null){
          traversePostOrder(node.left,list);
        
      }
      
      if(node.right != null){
          traversePostOrder(node.right,list);
      }
          list.add(node.value);
            // this first adds the left nodes values to the list before the right then go back up to right left most
      return list;
  }
  @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);

print(tree.DFSPostOrder(tree.root, []));
// 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;
// }
}