Trees

class BST { TreeNode root; // Insert TreeNode insert(TreeNode node, int val) { if (node == null) return new TreeNode(val); if (val < node.val) node.left = insert(node.left, val); else if (val > node.val) node.right = insert(node.right, val); return node; } // Search boolean search(TreeNode node, int val) { if (node == null) return false; if (val == node.val) return true; if (val < node.val) return search(node.left, val); return search(node.right, val); } // Traversals void inorder(TreeNode node) { // Left → Root → Right (sorted for BST) if (node == null) return; inorder(node.left); System.out.print(node.val + " "); inorder(node.right); } void preorder(TreeNode node) { // Root → Left → Right if (node == null) return; System.out.print(node.val + " "); preorder(node.left); preorder(node.right); } void postorder(TreeNode node) { // Left → Right → Root if (node == null) return; postorder(node.left); postorder(node.right); System.out.print(node.val + " "); } // Level order (BFS) void levelOrder(TreeNode root) { if (root == null) return; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode node = q.poll(); System.out.print(node.val + " "); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } System.out.println(); // New level } } // Height of tree int height(TreeNode node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } // Diameter (longest path between any two nodes) int diameter(TreeNode node) { if (node == null) return 0; int throughRoot = height(node.left) + height(node.right); int leftDiam = diameter(node.left); int rightDiam = diameter(node.right); return Math.max(throughRoot, Math.max(leftDiam, rightDiam)); } }