Trees & Graphs

// Binary Tree implementation in Java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    TreeNode root;
    
    public BinaryTree() {
        root = null;
    }
    
    // Insert a new node
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private TreeNode insertRec(TreeNode root, int val) {
        // If the tree is empty, create a new node
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        
        // Otherwise, recur down the tree
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        
        // Return the unchanged node pointer
        return root;
    }
    
    // Inorder traversal
    public void inorder() {
        inorderRec(root);
    }
    
    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }
    
    // Search for a node
    public boolean search(int val) {
        return searchRec(root, val);
    }
    
    private boolean searchRec(TreeNode root, int val) {
        // Base case: root is null or value is present at root
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        
        // Value is greater than root's value
        if (root.val < val) {
            return searchRec(root.right, val);
        }
        
        // Value is less than root's value
        return searchRec(root.left, val);
    }
}

// Graph implementation in Java using adjacency list
import java.util.*;

class Graph {
    private int V; // Number of vertices
    private LinkedList<Integer>[] adj; // Adjacency list
    
    // Constructor
    @SuppressWarnings("unchecked")
    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }
    
    // Add an edge to the graph
    public void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's list
    }
    
    // BFS traversal from a given source
    public void BFS(int s) {
        // Mark all vertices as not visited
        boolean[] visited = new boolean[V];
        
        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<>();
        
        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.add(s);
        
        while (!queue.isEmpty()) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s + " ");
            
            // Get all adjacent vertices of the dequeued vertex
            // If an adjacent has not been visited, mark it visited and enqueue it
            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
    
    // DFS traversal from a given source
    public void DFS(int s) {
        // Mark all vertices as not visited
        boolean[] visited = new boolean[V];
        
        // Call the recursive helper function to print DFS traversal
        DFSUtil(s, visited);
    }
    
    // A recursive function used by DFS
    private void DFSUtil(int v, boolean[] visited) {
        // Mark the current node as visited and print it
        visited[v] = true;
        System.out.print(v + " ");
        
        // Recur for all the vertices adjacent to this vertex
        for (int n : adj[v]) {
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }
}