BST

package LAB5;
import java.util.*;

public class BinarySearchTree {
    private Node root;

    public BinarySearchTree() {
        root = null;
    }

    public boolean insert(Number value) {
        Node newNode = new Node(value);

        if (root == null) {
            root = newNode;
            return true;
        }

        Node temp = root;

        while (true) {
            if (newNode.value.doubleValue() == temp.value.doubleValue()) return false;

            if (newNode.value.doubleValue() < temp.value.doubleValue()) {
                if (temp.left == null) {
                    temp.left = newNode;
                    return true;
                }
                temp = temp.left;
            } else {
                if (temp.right == null) {
                    temp.right = newNode;
                    return true;
                }
                temp = temp.right;
            }
        }
    }

    public boolean contains(Number value) {
        if (root == null) return false;

        Node temp = root;

        while (temp != null) {
            if (value.doubleValue() < temp.value.doubleValue()) {
                temp = temp.left;
            } else if (value.doubleValue() > temp.value.doubleValue()) {
                temp = temp.right;
            } else if (value.doubleValue() == temp.value.doubleValue()) {
                return true;
            }
        }
        return false;
    }

    public boolean delete(Number value) {
        Node parentNode = null;
        Node currentNode = root;
        boolean isLeftChild = false;

        while (currentNode != null && currentNode.value.doubleValue() != value.doubleValue()) {
            parentNode = currentNode;
            if (value.doubleValue() < currentNode.value.doubleValue()) {
                currentNode = currentNode.left;
                isLeftChild = true;
            } else {
                currentNode = currentNode.right;
                isLeftChild = false;
            }
        }

        if (currentNode == null) {
            return false;
        }

        if (currentNode.left == null && currentNode.right == null) {
            if (currentNode == root) {
                root = null;
            } else if (isLeftChild) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
        } else if (currentNode.left == null) {
            if (currentNode == root) {
                root = currentNode.right;
            } else if (isLeftChild) {
                parentNode.left = currentNode.right;
            } else {
                parentNode.right = currentNode.right;
            }
        } else if (currentNode.right == null) {
            if (currentNode == root) {
                root = currentNode.left;
            } else if (isLeftChild) {
                parentNode.left = currentNode.left;
            } else {
                parentNode.right = currentNode.left;
            }
        } else {
            Node successor = getSuccessor(currentNode);
            if (currentNode == root) {
                root = successor;
            } else if (isLeftChild) {
                parentNode.left = successor;
            } else {
                parentNode.right = successor;
            }
            successor.left = currentNode.left;
        }
        return true;
    }

    private Node getSuccessor(Node deleteNode) {
        Node successorParent = deleteNode;
        Node successor = deleteNode;
        Node currentNode = deleteNode.right;

        while (currentNode != null) {
            successorParent = successor;
            successor = currentNode;
            currentNode = currentNode.left;
        }

        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }
        return successor;
    }

    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(Node currentNode) {
        if (currentNode != null) {
            inOrderTraversal(currentNode.left);
            System.out.print(currentNode.value + " ");
            inOrderTraversal(currentNode.right);
        }
    }

    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    private void preOrderTraversal(Node currentNode) {
        if (currentNode != null) {
            System.out.print(currentNode.value + " ");
            preOrderTraversal(currentNode.left);
            preOrderTraversal(currentNode.right);
        }
    }

    public void postOrderTraversal() {
        postOrderTraversal(root);
    }

    private void postOrderTraversal(Node currentNode) {
        if (currentNode != null) {
            postOrderTraversal(currentNode.left);
            postOrderTraversal(currentNode.right);
            System.out.print(currentNode.value + " ");
        }
    }

    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(Node currentNode) {
        if (currentNode == null) {
            return 0;
        } else {
            int leftHeight = getHeight(currentNode.left);
            int rightHeight = getHeight(currentNode.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public int getNumberOfNodes() {
        return getNumberOfNodes(root);
    }

    private int getNumberOfNodes(Node currentNode) {
        if (currentNode == null) {
            return 0;
        } else {
            int leftCount = getNumberOfNodes(currentNode.left);
            int rightCount = getNumberOfNodes(currentNode.right);
            return leftCount + rightCount + 1;
        }
    }

    public class Node {
        Number value;
        Node left;
        Node right;

        public Node(Number value) {
            this.value = value;
            left = null;
            right = null;
        }
    }

    public List<Number> findNodesWithGivenChildren(int numberOfChildren)
    {
        List<Number> nodes = new ArrayList<>();
        findNodesWithGivenChildren(root, numberOfChildren, nodes);
        return nodes;
    }
    
    private void findNodesWithGivenChildren(Node currentNode, int numberOfChildren, List<Number> nodes)
    {
        if (currentNode != null)
        {
            int childrenCount = 0;
            if (currentNode.left != null)
            {
                childrenCount++;
                findNodesWithGivenChildren(currentNode.left, numberOfChildren, nodes);
            }
            if (currentNode.right != null)
            {
                childrenCount++;
                findNodesWithGivenChildren(currentNode.right, numberOfChildren, nodes);
            }
            if (childrenCount == numberOfChildren)
            {
                nodes.add(currentNode.value);
            }
        }
    }
    
    
}