import java.util.*;

public class Main {

    // Binary Search Tree (BST) implementation
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // Method to find the height of a BST
    public static int findBSTHeight(TreeNode root) {
        if (root == null)
            return 0;
        int leftHeight = findBSTHeight(root.left);
        int rightHeight = findBSTHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Hash Table implementation using separate chaining
    public static class ListNode {
        String key;
        int value;
        ListNode next;

        public ListNode(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void deleteFromHashTable(ListNode[] hashTable, String key) {
        int index = Math.abs(key.hashCode() % hashTable.length);
        if (hashTable[index] != null) {
            ListNode prev = null;
            ListNode current = hashTable[index];
            while (current != null) {
                if (current.key.equals(key)) {
                    if (prev == null) {
                        hashTable[index] = current.next;
                    } else {
                        prev.next = current.next;
                    }
                    break;
                }
                prev = current;
                current = current.next;
            }
        }
    }

    // Breadth-first Search (BFS) traversal on a graph represented as an adjacency list
    public static List<Integer> bfsTraversal(Map<Integer, List<Integer>> graph, int start) {
        List<Integer> visited = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                List<Integer> neighbors = graph.getOrDefault(vertex, new ArrayList<>());
                for (int neighbor : neighbors) {
                    queue.offer(neighbor);
                }
            }
        }

        return visited;
    }

    public static void main(String[] args) {
        // Testing the implemented methods
        // Example usage for BST height calculation
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println("Height of the BST: " + findBSTHeight(root));

        // Example usage for Hash Table deletion
        ListNode[] hashTable = new ListNode[10];
        insert(hashTable, "apple", 5);
        insert(hashTable, "banana", 8);
        System.out.println("Before deletion: " + Arrays.toString(hashTable));
        deleteFromHashTable(hashTable, "banana");
        System.out.println("After deletion: " + Arrays.toString(hashTable));

        // Example usage for BFS traversal
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(2));
        graph.put(2, Arrays.asList(0, 3));
        graph.put(3, Arrays.asList(3));
        System.out.println("BFS traversal: " + bfsTraversal(graph, 0));
    }

    public static void insert(ListNode[] hashTable, String key, int value) {
        int index = Math.abs(key.hashCode() % hashTable.length);
        if (hashTable[index] == null) {
            hashTable[index] = new ListNode(key, value);
        } else {
            ListNode current = hashTable[index];
            while (current.next != null) {
                current = current.next;
            }
            current.next = new ListNode(key, value);
        }
    }
}