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;
}
*/
}
}
class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(9);
bst.insert(10);
bst.insert(8);
bst.remove(8);
System.out.println("6:"+bst.lookup(6));
System.out.println("10:"+bst.lookup(10));
bst.traverse();
}
}
