BST

import java.util.Queue;
import java.util.LinkedList;
import java.util.List;

class TreeNode{
    private TreeNode left=null;
    private TreeNode right= null;
    private int value;
    
    public TreeNode(int value){
        this.value = value;
    }
    
    public void setLeft(TreeNode left){
        this.left= left;
    }
    public void setRight(TreeNode right){
        this.right= right;
        
    }
    
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }
    
    public int getValue(){
        return this.value;
    }
}


class BinarySearchTree{
    private TreeNode root=null;
    
    public BinarySearchTree(){
    }
    public boolean insert(int value){
        /*if (value == null || value.isEmpty()){
            System.out.println("The value cannot be null or empty.");
            return;
        }*/
        if (root == null){
            root = new TreeNode(value);
            return true;
        }
        TreeNode newNode = new TreeNode(value);
        insertNode(root, newNode);
        return true;
    }
    public void insertNode(TreeNode startNode, TreeNode newNode){
        TreeNode currentNode = startNode;
        
        while (currentNode != null) {
            if (newNode.getValue() > currentNode.getValue()){
                if (currentNode.getRight() != null){
                    currentNode = currentNode.getRight();    
                } else {
                    currentNode.setRight(newNode);
                    break;
                }
            } else {
                if (currentNode.getLeft() != null){
                    currentNode = currentNode.getLeft();    
                }  else {
                    currentNode.setLeft(newNode);
                    break;
                }
            }
        }
    }
    
    
    public boolean lookup(int value){
        TreeNode currentNode = root;
        
        while (currentNode != null) {
            if (value > currentNode.getValue()){
                if (currentNode.getRight() != null){
                    currentNode = currentNode.getRight();    
                } else {
                    break;
                }
            } else if (value < currentNode.getValue()){
                if (currentNode.getLeft() != null){
                    currentNode = currentNode.getLeft();    
                } else {
                    break;
                }
            } else {
                return true;
            }
        }
        return false;
    }
    
    public boolean remove (int value){
        TreeNode currentNode = this.root;
        TreeNode previousNode = null;
        
        while (currentNode != null){
            if (value > currentNode.getValue()){
                previousNode = currentNode;
                currentNode = currentNode.getRight();
            } else if (value < currentNode.getValue()){
                previousNode = currentNode;
                currentNode = currentNode.getLeft();
            } else if (value == currentNode.getValue()){
                TreeNode removedNode = currentNode;
                TreeNode parentNewNode= currentNode;
                
                currentNode = currentNode.getRight();
                if (currentNode == null){
                    if (previousNode.getLeft().getValue() == parentNewNode.getValue()){
                        previousNode.setLeft(null);
                    }else if (previousNode.getRight().getValue() == parentNewNode.getValue()){
                        previousNode.setRight(null);
                    }
                        
                } else if (currentNode != null){
                    while (currentNode.getLeft() != null){
                        parentNewNode=currentNode;
                        currentNode=currentNode.getLeft();
                    }
                    if (previousNode.getLeft().getValue() == removedNode.getValue()){
                        previousNode.setLeft(currentNode);
                        currentNode.setLeft(removedNode.getLeft());
                        currentNode.setRight(removedNode.getRight());
                        parentNewNode.setLeft(null);
                        
                    }
            
                }
                return true;
            }
        }
        return false;
    }
    
    public void traverse(){
        traverse(root);
    }
    public void traverse(TreeNode startNode){
        TreeNode currentNode =startNode;
        
        System.out.println(currentNode.getValue());
        if (currentNode.getLeft() != null){
            traverse(currentNode.getLeft());
        }
        if (currentNode.getRight() != null){
            traverse(currentNode.getRight());
        }
        /*
             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;
  }
        */
        
        
    }
    
    
    public List<Integer> bfs(){
        Queue queue = new LinkedList();
        TreeNode node = root;
        List<Integer> list = new LinkedList<Integer>();
        
        queue.add(node);
        
        while (!queue.isEmpty()){
            node = (TreeNode)queue.remove();
            if (node.getLeft() != null){
                queue.add(node.getLeft());
                
            }
            if (node.getRight() != null){
                queue.add(node.getRight());
            }
            
            list.add(node.getValue());
        }
        return list;
    }
    
    public List<Integer> bfsR(Queue queue, List list){
        if (!queue.isEmpty()){
            return list;
        }
        
        
        Node node = (TreeNode)queue.remove();
        if (node.getLeft() != null){
            queue.add(node.getLeft());
            
        }
        if (node.getRight() != null){
            queue.add(node.getRight());
        }
        list.add(node.getValue());
        return bfsR(queue, list);
    }
    
    public void dfsInOrder(Node node, List list){
        return traverseInOrder(node, list);
    }
    
    public List traverseInOrder(Node node, List list){
        if (node == null){
            return list;
        }
    }
}


class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(9);
        bst.insert(6);
        bst.insert(12);
        bst.insert(1);
        bst.insert(4);
        bst.insert(34);
        bst.insert(45);
        List<Integer> list = bst.bfs();
        for (Integer element : list){
            System.out.println(element);
        }
    }
}