'use client'; import React, { useState, useEffect, useRef, useMemo } from 'react'; // --- Types & Constants --- type Node = { id: number; value: number; x: number; y: number; left?: number; right?: number; parent?: number; depth: number; }; type Edge = { from: number; to: number; }; const VIEW_WIDTH = 1000; const VIEW_HEIGHT = 700; const NODE_RADIUS = 22; const ANIMATION_DELAY = 700; // Colors const COLORS = { bg: '#0f172a', // Slate 900 nodeDefault: '#334155', // Slate 700 nodeActive: '#f59e0b', // Amber 500 nodeVisited: '#10b981', // Emerald 500 nodeInQueue: '#3b82f6', // Blue 500 edgeDefault: '#1e293b', // Slate 800 edgeActive: '#f59e0b', text: '#f8fafc', grid: '#1e293b', }; // --- Helper: Generate Binary Tree --- const generateTree = (): { nodes: Node[]; edges: Edge[] } => { const nodes: Node[] = []; const edges: Edge[] = []; const levels = 4; // Root nodes.push({ id: 0, value: 1, x: VIEW_WIDTH / 2, y: 80, depth: 0 }); let queue = [0]; let idCounter = 1; // Simple generation logic for a balanced-ish tree while (queue.length > 0) { const parentId = queue.shift()!; const parent = nodes.find(n => n.id === parentId)!; if (parent.depth < levels - 1) { // Determine spread based on depth to avoid overlap const spread = VIEW_WIDTH / Math.pow(2, parent.depth + 2); // Left Child const leftId = idCounter++; nodes.push({ id: leftId, value: Math.floor(Math.random() * 100), x: parent.x - spread, y: parent.y + 100, depth: parent.depth + 1, parent: parentId }); edges.push({ from: parentId, to: leftId }); parent.left = leftId; queue.push(leftId); // Right Child const rightId = idCounter++; nodes.push({ id: rightId, value: Math.floor(Math.random() * 100), x: parent.x + spread, y: parent.y + 100, depth: parent.depth + 1, parent: parentId }); edges.push({ from: parentId, to: rightId }); parent.right = rightId; queue.push(rightId); } } return { nodes, edges }; }; export const BinaryTreeTraversal = () => { // --- State --- const [tree, setTree] = useState(generateTree()); const [visited, setVisited] = useState([]); const [activeNode, setActiveNode] = useState(null); const [dsContent, setDsContent] = useState([]); // Stack or Queue content const [mode, setMode] = useState<'BFS' | 'DFS'>('DFS'); const [isAnimating, setIsAnimating] = useState(false); // Refs for async control const stopRef = useRef(false); // --- Animation Logic --- const runTraversal = async (algorithm: 'BFS' | 'DFS') => { if (isAnimating) return; setIsAnimating(true); stopRef.current = false; // Reset states setVisited([]); setActiveNode(null); setDsContent([]); const { nodes } = tree; const root = nodes[0]; if (!root) return; // Data Structure (Stack for DFS, Queue for BFS) // We use a generic array and treat it differently based on mode const dataStructure: number[] = [root.id]; const visitedSet = new Set(); setDsContent([...dataStructure]); while (dataStructure.length > 0) { if (stopRef.current) break; // Logic difference: DFS pops from end, BFS shifts from start // However, for visualization consistency in the array, let's just use pop/shift logic let currentId: number; if (algorithm === 'DFS') { // DFS: Stack (LIFO) - Pop from end currentId = dataStructure.pop()!; } else { // BFS: Queue (FIFO) - Shift from start currentId = dataStructure.shift()!; } setActiveNode(currentId); setDsContent([...dataStructure]); // Update visual queue/stack BEFORE processing children (removed item) // Animate "Processing" await new Promise(r => setTimeout(r, ANIMATION_DELAY)); if (stopRef.current) break; if (!visitedSet.has(currentId)) { visitedSet.add(currentId); setVisited(prev => [...prev, currentId]); const currentNode = nodes.find(n => n.id === currentId)!; // Add neighbors // For DFS (Pre-order): Right then Left pushed to stack, so Left is popped first // For BFS (Level-order): Left then Right pushed to queue const children = []; if (currentNode.left !== undefined) children.push(currentNode.left); if (currentNode.right !== undefined) children.push(currentNode.right); if (algorithm === 'DFS') { // Push Right then Left to stack so Left comes out first if (currentNode.right !== undefined) dataStructure.push(currentNode.right); if (currentNode.left !== undefined) dataStructure.push(currentNode.left); } else { // Push Left then Right to queue if (currentNode.left !== undefined) dataStructure.push(currentNode.left); if (currentNode.right !== undefined) dataStructure.push(currentNode.right); } // Update visual DS after adding children setDsContent([...dataStructure]); } await new Promise(r => setTimeout(r, ANIMATION_DELAY / 2)); } setActiveNode(null); setIsAnimating(false); }; const handleReset = () => { stopRef.current = true; setVisited([]); setActiveNode(null); setDsContent([]); setIsAnimating(false); setTimeout(() => { setTree(generateTree()); }, 100); }; const handleStart = () => { if (isAnimating) return; runTraversal(mode); }; // --- Render Helpers --- const getNodeColor = (id: number) => { if (activeNode === id) return COLORS.nodeActive; if (visited.includes(id)) return COLORS.nodeVisited; if (dsContent.includes(id)) return COLORS.nodeInQueue; return COLORS.nodeDefault; }; return ( ); };