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