BST Class

package LAB4;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree
{
    public Node root;

    public BinarySearchTree(int[] values)
    {
        root = constructBST(values, 0);
    }

    private Node constructBST(int[] values, int index)
    {
        if (index < values.length)
        {
            Node node = new Node(values[index]);
            node.left = constructBST(values, 2 * index + 1);
            node.right = constructBST(values, 2 * index + 2);
            return node;
        }
        return null;
    }

    public boolean insert(int value)
    {
        // Create a new node with the given value
        Node newNode = new Node(value);

        // If the root is null, it means the tree is empty, so the new node becomes the root
        if (root == null)
        {
            root = newNode;
            return true;
        }

        // Initialize a temporary node to navigate the tree
        Node temp = root;

        // Keep looping until we find the appropriate position to insert the new node
        while (true)
        {
           /* // If the new node's value is equal to the current node's 
           value, the value already exists in the tree, so we return false */
            if (newNode.value == temp.value) return false;

           /* // If the new node's value is less than the current node's value, 
           we go to the left subtree */
            if (newNode.value < temp.value)
            {
               /* // If the left child of the current node is null, 
               it means this is the correct position to insert the new node */
                if (temp.left == null)
                {
                    temp.left = newNode;
                    return true;
                }
                // Move to the left child
                temp = temp.left;
            }
            /*// If the new node's value is greater than the current node's value,
             we go to the right subtree */
            else 
            {
                /*// If the right child of the current node is null, 
                it means this is the correct position to insert the new node */
                if (temp.right == null)
                {
                    temp.right = newNode;
                    return true;
                }
                // Move to the right child
                temp = temp.right;
            }
        }
    }


    public boolean contains(int value)
    {
       /* // If the root is null, it means the tree is empty,
        so the value is not in the tree, return false */
        if (root == null) return false;

        // Initialize a temporary node to navigate the tree
        Node temp = root;

        // Keep looping until we reach the end of the tree or find the value
        while (temp != null)
        {
            /* If the value we are searching for is less than the current node's value,
             we go to the left subtree */
            if (value < temp.value)
            {
                temp = temp.left;
            }
            /*// If the value we are searching for is greater than the current node's value,
             we go to the right subtree */
            else if (value > temp.value)
            {
                temp = temp.right;
            }
            /*// If the value we are searching for is equal to the current node's value,
             the value is in the tree, return true */
            else if (value == temp.value)
            {
                return true;
            }
        }
        // If we reached the end of the tree and did not find the value, return false
        return false;
    }


    public Node getRoot()
    {
        return root;
    }

    public ArrayList<Integer> BFS()
    {
        // Initialize the current node to the root of the binary search tree
        Node currentNode = root;
        
        // Initialize a queue to store nodes for the BFS traversal
        Queue<Node> queue = new LinkedList<>();
        
        // Initialize an ArrayList to store the result of the BFS traversal
        ArrayList<Integer> results = new ArrayList<>();
        
        // Add the root node to the queue to start the traversal
        queue.add(currentNode);
    
        /*// Keep looping until the queue is empty, 
        which means we have visited all the nodes in the tree */
        while (queue.size() > 0)
        {
            // Remove the first node from the queue and update the current node
            currentNode = queue.remove();
            
            // Add the value of the current node to the results ArrayList
            results.add(currentNode.value);
    
            // If the current node has a left child, add it to the queue
            if (currentNode.left != null)
            {
                queue.add(currentNode.left);
            }
            
            // If the current node has a right child, add it to the queue
            if (currentNode.right != null)
            {
                queue.add(currentNode.right);
            }
        }
        
        // Return the ArrayList containing the result of the BFS traversal
        return results;
    }
    public ArrayList<Integer> DFSPreOrder()
    {
        // Initialize an ArrayList to store the result of the Pre-order DFS traversal
        ArrayList<Integer> results = new ArrayList<>();

        // Call the helper method to perform Pre-order DFS traversal starting from the root node
        traversePreOrder(root, results);

        // Return the ArrayList containing the result of the Pre-order DFS traversal
        return results;
    }

    public ArrayList<Integer> DFSPostOrder()
    {
        // Initialize an ArrayList to store the result of the Post-order DFS traversal
        ArrayList<Integer> results = new ArrayList<>();

        // Call the helper method to perform Post-order DFS traversal starting from the root node
        traversePostOrder(root, results);

        // Return the ArrayList containing the result of the Post-order DFS traversal
        return results;
    }

    public ArrayList<Integer> DFSInOrder()
    {
        // Initialize an ArrayList to store the result of the In-order DFS traversal
        ArrayList<Integer> results = new ArrayList<>();

        // Call the helper method to perform In-order DFS traversal starting from the root node
        traverseInOrder(root, results);

        // Return the ArrayList containing the result of the In-order DFS traversal
        return results;
    }

        // Helper method to perform Pre-order DFS traversal
    private void traversePreOrder(Node node, ArrayList<Integer> results)
    {
        // Base case: if the current node is null, return
        if (node == null)
        {
            return;
        }

        // Add the current node's value to the results list
        results.add(node.value);

        // Recursively traverse the left subtree
        traversePreOrder(node.left, results);

        // Recursively traverse the right subtree
        traversePreOrder(node.right, results);
    }

    // Helper method to perform In-order DFS traversal
    private void traverseInOrder(Node node, ArrayList<Integer> results)
    {
        // Base case: if the current node is null, return
        if (node == null)
        {
            return;
        }

        // Recursively traverse the left subtree
        traverseInOrder(node.left, results);

        // Add the current node's value to the results list
        results.add(node.value);

        // Recursively traverse the right subtree
        traverseInOrder(node.right, results);
    }

    // Helper method to perform Post-order DFS traversal
    private void traversePostOrder(Node node, ArrayList<Integer> results)
    {
        // Base case: if the current node is null, return
        if (node == null)
        {
            return;
        }

        // Recursively traverse the left subtree
        traversePostOrder(node.left, results);

        // Recursively traverse the right subtree
        traversePostOrder(node.right, results);

        // Add the current node's value to the results list
        results.add(node.value);
    }



    public ArrayList<Integer> convertToPostOrder(ArrayList<Integer> preorder, ArrayList<Integer> inorder)
    {
        // Construct the binary tree using the given Pre-order and In-order traversal results
        Node constructedRoot = buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    
        // Initialize an ArrayList to store the result of the Post-order traversal
        ArrayList<Integer> postOrder = new ArrayList<>();
    
        // Call the helper method to perform Post-order traversal on the constructed tree
        traversePostOrder(constructedRoot, postOrder);
    
        // Return the ArrayList containing the result of the Post-order traversal
        return postOrder;
    }
    
    private Node buildTree(ArrayList<Integer> preorder, int preStart, int preEnd, ArrayList<Integer> inorder, int inStart, int inEnd)
    {
        // If the Pre-order or In-order subarray indices are out of bounds, return null
        if (preStart > preEnd || inStart > inEnd)
        {
            return null;
        }
    
        // Get the root value from the Pre-order traversal result
        int rootValue = preorder.get(preStart);
        Node root = new Node(rootValue);
    
        // Find the index of the root value in the In-order traversal result
        int k = 0;
        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder.get(i) == rootValue)
            {
                k = i;
                break;
            }
        }
    
        /*// Recursively build the left and right subtrees using 
        the Pre-order and In-order traversal results */
        root.left = buildTree(preorder, preStart + 1, preStart + (k - inStart), inorder, inStart, k - 1);
        root.right = buildTree(preorder, preStart + (k - inStart) + 1, preEnd, inorder, k + 1, inEnd);
    
        // Return the constructed binary tree root
        return root;
    }
    

}