Ejemplos de Estructuras de Datos Web Go

// Web Go Slices and Arrays Examples
// Working with Go slices and arrays

package main

import (
	"fmt"
	"sort"
	"strings"
)

// 1. Creating Slices

// CreateSlicesExample demonstrates various ways to create slices
func CreateSlicesExample() {
	fmt.Println("--- Creating Slices ---")

	// Method 1: Using make
	slice1 := make([]int, 5)       // Creates slice of length 5
	slice2 := make([]int, 3, 10)   // Creates slice of length 3, capacity 10
	fmt.Printf("slice1: %v (len=%d, cap=%d)\n", slice1, len(slice1), cap(slice1))
	fmt.Printf("slice2: %v (len=%d, cap=%d)\n", slice2, len(slice2), cap(slice2))

	// Method 2: Slice literal
	slice3 := []int{1, 2, 3, 4, 5}
	fmt.Printf("slice3: %v\n", slice3)

	// Method 3: From array
	array := [5]int{1, 2, 3, 4, 5}
	slice4 := array[1:4] // Creates slice [2, 3, 4]
	fmt.Printf("slice4: %v\n", slice4)

	// Method 4: Empty slice
	var slice5 []int
	fmt.Printf("slice5: %v (nil=%v)\n", slice5, slice5 == nil)
}

// 2. Adding Elements

// AddElementsExample demonstrates adding elements to slices
func AddElementsExample() {
	fmt.Println("\n--- Adding Elements ---")

	slice := []int{1, 2, 3}

	// Append single element
	slice = append(slice, 4)
	fmt.Printf("After append(4): %v\n", slice)

	// Append multiple elements
	slice = append(slice, 5, 6, 7)
	fmt.Printf("After append(5,6,7): %v\n", slice)

	// Append another slice
	anotherSlice := []int{8, 9, 10}
	slice = append(slice, anotherSlice...)
	fmt.Printf("After append(anotherSlice): %v\n", slice)
}

// 3. Accessing and Modifying Elements

// AccessModifyExample demonstrates accessing and modifying elements
func AccessModifyExample() {
	fmt.Println("\n--- Accessing and Modifying ---")

	slice := []string{"apple", "banana", "cherry"}

	// Access elements
	fmt.Printf("First element: %s\n", slice[0])
	fmt.Printf("Last element: %s\n", slice[len(slice)-1])

	// Modify elements
	slice[1] = "blueberry"
	fmt.Printf("After modification: %v\n", slice)

	// Using range to access
	fmt.Print("Using range: ")
	for i, value := range slice {
		fmt.Printf("[%d]=%s ", i, value)
	}
	fmt.Println()
}

// 4. Slicing Operations

// SlicingExample demonstrates slice operations
func SlicingExample() {
	fmt.Println("\n--- Slicing Operations ---")

	slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

	// Different slicing operations
	fmt.Printf("Original: %v\n", slice)
	fmt.Printf("slice[2:5]: %v\n", slice[2:5])   // [2 3 4]
	fmt.Printf("slice[:5]: %v\n", slice[:5])      // [0 1 2 3 4]
	fmt.Printf("slice[5:]: %v\n", slice[5:])      // [5 6 7 8 9]
	fmt.Printf("slice[:]: %v\n", slice[:])       // [0 1 2 3 4 5 6 7 8 9]

	// Create sub-slice
	subSlice := slice[3:7]
	fmt.Printf("subSlice: %v\n", subSlice)
}

// 5. Deleting Elements

// DeleteElementsExample demonstrates deleting elements from slices
func DeleteElementsExample() {
	fmt.Println("\n--- Deleting Elements ---")

	slice := []int{1, 2, 3, 4, 5, 6, 7}

	// Delete first element
	slice = slice[1:]
	fmt.Printf("Delete first: %v\n", slice)

	// Delete last element
	slice = slice[:len(slice)-1]
	fmt.Printf("Delete last: %v\n", slice)

	// Delete middle element (index 2)
	index := 2
	slice = append(slice[:index], slice[index+1:]...)
	fmt.Printf("Delete index %d: %v\n", index, slice)

	// Delete multiple elements (remove elements at indices 1-2)
	slice = append(slice[:1], slice[3:]...)
	fmt.Printf("Delete range [1:3]: %v\n", slice)
}

// 6. Copying Slices

// CopySlicesExample demonstrates copying slices
func CopySlicesExample() {
	fmt.Println("\n--- Copying Slices ---")

	original := []int{1, 2, 3, 4, 5}

	// Method 1: Using copy
	copied := make([]int, len(original))
	copy(copied, original)
	fmt.Printf("Original: %v\n", original)
	fmt.Printf("Copied: %v\n", copied)

	// Modify copy
	copied[0] = 999
	fmt.Printf("After modifying copy: %v\n", copied)
	fmt.Printf("Original unchanged: %v\n", original)

	// Method 2: Using append
	copied2 := append([]int{}, original...)
	fmt.Printf("Copied2: %v\n", copied2)
}

// 7. Sorting Slices

// SortSlicesExample demonstrates sorting operations
func SortSlicesExample() {
	fmt.Println("\n--- Sorting Slices ---")

	// Sort integers
	numbers := []int{5, 2, 8, 1, 9, 3}
	sort.Ints(numbers)
	fmt.Printf("Sorted integers: %v\n", numbers)

	// Sort strings
	fruits := []string{"banana", "apple", "cherry"}
	sort.Strings(fruits)
	fmt.Printf("Sorted strings: %v\n", fruits)

	// Custom sort with reverse
	numbers2 := []int{5, 2, 8, 1, 9, 3}
	sort.Sort(sort.Reverse(sort.IntSlice(numbers2)))
	fmt.Printf("Reverse sorted: %v\n", numbers2)

	// Check if sorted
	isSorted := sort.IntsAreSorted(numbers)
	fmt.Printf("Is sorted: %v\n", isSorted)
}

// 8. Searching Slices

// SearchSlicesExample demonstrates searching in slices
func SearchSlicesExample() {
	fmt.Println("\n--- Searching Slices ---")

	slice := []string{"apple", "banana", "cherry", "date"}

	// Linear search
	target := "cherry"
	found := false
	index := -1

	for i, v := range slice {
		if v == target {
			found = true
			index = i
			break
		}
	}

	if found {
		fmt.Printf("Found '%s' at index %d\n", target, index)
	} else {
		fmt.Printf("'%s' not found\n", target)
	}

	// Binary search (requires sorted slice)
	sort.Strings(slice)
	target = "banana"
	index = sort.SearchStrings(slice, target)
	if index < len(slice) && slice[index] == target {
		fmt.Printf("Binary search found '%s' at index %d\n", target, index)
	}
}

// 9. Filtering Slices

// FilterSlicesExample demonstrates filtering operations
func FilterSlicesExample() {
	fmt.Println("\n--- Filtering Slices ---")

	numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

	// Filter even numbers
	var evens []int
	for _, num := range numbers {
		if num%2 == 0 {
			evens = append(evens, num)
		}
	}
	fmt.Printf("Even numbers: %v\n", evens)

	// Filter numbers greater than 5
	var greaterThanFive []int
	for _, num := range numbers {
		if num > 5 {
			greaterThanFive = append(greaterThanFive, num)
		}
	}
	fmt.Printf("Greater than 5: %v\n", greaterThanFive)
}

// 10. Transforming Slices (Map)

// TransformSlicesExample demonstrates slice transformation
func TransformSlicesExample() {
	fmt.Println("\n--- Transforming Slices ---")

	numbers := []int{1, 2, 3, 4, 5}

	// Double each element
	doubled := make([]int, len(numbers))
	for i, num := range numbers {
		doubled[i] = num * 2
	}
	fmt.Printf("Doubled: %v\n", doubled)

	// Convert to strings
	strings := make([]string, len(numbers))
	for i, num := range numbers {
		strings[i] = fmt.Sprintf("num_%d", num)
	}
	fmt.Printf("Strings: %v\n", strings)
}

// 11. Reducing Slices

// ReduceSlicesExample demonstrates reduce operations
func ReduceSlicesExample() {
	fmt.Println("\n--- Reducing Slices ---")

	numbers := []int{1, 2, 3, 4, 5}

	// Sum
	sum := 0
	for _, num := range numbers {
		sum += num
	}
	fmt.Printf("Sum: %d\n", sum)

	// Product
	product := 1
	for _, num := range numbers {
		product *= num
	}
	fmt.Printf("Product: %d\n", product)

	// Max
	max := numbers[0]
	for _, num := range numbers {
		if num > max {
			max = num
		}
	}
	fmt.Printf("Max: %d\n", max)

	// Min
	min := numbers[0]
	for _, num := range numbers {
		if num < min {
			min = num
		}
	}
	fmt.Printf("Min: %d\n", min)
}

// 12. Multidimensional Slices

// MultiDimExample demonstrates multidimensional slices
func MultiDimExample() {
	fmt.Println("\n--- Multidimensional Slices ---")

	// Create 2D slice
	matrix := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}

	fmt.Println("Matrix:")
	for i, row := range matrix {
		fmt.Printf("Row %d: %v\n", i, row)
	}

	// Access elements
	fmt.Printf("matrix[1][2] = %d\n", matrix[1][2])

	// Create triangular slice
	triangular := [][]int{
		{1},
		{2, 3},
		{4, 5, 6},
	}

	fmt.Println("\nTriangular:")
	for i, row := range triangular {
		fmt.Printf("Row %d: %v\n", i, row)
	}
}

// 13. Common Slice Algorithms

// CommonAlgorithmsExample demonstrates common algorithms
func CommonAlgorithmsExample() {
	fmt.Println("\n--- Common Algorithms ---")

	// Reverse slice
	slice := []int{1, 2, 3, 4, 5}
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
	fmt.Printf("Reversed: %v\n", slice)

	// Remove duplicates
	duplicates := []int{1, 2, 2, 3, 4, 4, 5}
	unique := make([]int, 0)
	seen := make(map[int]bool)

	for _, num := range duplicates {
		if !seen[num] {
			seen[num] = true
			unique = append(unique, num)
		}
	}
	fmt.Printf("Unique: %v\n", unique)

	// Intersection
	slice1 := []int{1, 2, 3, 4, 5}
	slice2 := []int{4, 5, 6, 7, 8}

	intersection := []int{}
	set := make(map[int]bool)

	for _, num := range slice2 {
		set[num] = true
	}

	for _, num := range slice1 {
		if set[num] {
			intersection = append(intersection, num)
		}
	}
	fmt.Printf("Intersection: %v\n", intersection)
}

// 14. Slice Utilities

// SliceContains checks if slice contains element
func SliceContains(slice []string, element string) bool {
	for _, v := range slice {
		if v == element {
			return true
		}
	}
	return false
}

// SliceIndex returns index of element or -1
func SliceIndex(slice []string, element string) int {
	for i, v := range slice {
		if v == element {
			return i
		}
	}
	return -1
}

// SliceJoin joins slice elements with separator
func SliceJoin(slice []string, sep string) string {
	return strings.Join(slice, sep)
}

// SliceUtilitiesExample demonstrates utility functions
func SliceUtilitiesExample() {
	fmt.Println("\n--- Slice Utilities ---")

	fruits := []string{"apple", "banana", "cherry"}

	// Contains
	fmt.Printf("Contains 'banana': %v\n", SliceContains(fruits, "banana"))
	fmt.Printf("Contains 'grape': %v\n", SliceContains(fruits, "grape"))

	// Index
	fmt.Printf("Index of 'cherry': %d\n", SliceIndex(fruits, "cherry"))

	// Join
	fmt.Printf("Joined: %s\n", SliceJoin(fruits, ", "))
}

// Main function
func main() {
	fmt.Println("=== Web Go Slices and Arrays Examples ===\n")

	CreateSlicesExample()
	AddElementsExample()
	AccessModifyExample()
	SlicingExample()
	DeleteElementsExample()
	CopySlicesExample()
	SortSlicesExample()
	SearchSlicesExample()
	FilterSlicesExample()
	TransformSlicesExample()
	ReduceSlicesExample()
	MultiDimExample()
	CommonAlgorithmsExample()
	SliceUtilitiesExample()

	fmt.Println("\n=== All Slices and Arrays Examples Completed ===")
}

// Web Go Maps and Dictionaries Examples
// Working with Go maps for key-value storage

package main

import (
	"fmt"
	"sort"
	"strings"
)

// 1. Creating Maps

// CreateMapsExample demonstrates various ways to create maps
func CreateMapsExample() {
	fmt.Println("--- Creating Maps ---")

	// Method 1: Using make
	map1 := make(map[string]int)
	fmt.Printf("Empty map: %v\n", map1)

	// Method 2: Map literal
	map2 := map[string]int{
		"apple":  5,
		"banana": 3,
		"cherry": 8,
	}
	fmt.Printf("Map literal: %v\n", map2)

	// Method 3: Empty map
	var map3 map[string]int
	fmt.Printf("Nil map: %v (nil=%v)\n", map3, map3 == nil)
}

// 2. Adding and Updating Elements

// AddUpdateElementsExample demonstrates adding/updating map entries
func AddUpdateElementsExample() {
	fmt.Println("\n--- Adding and Updating Elements ---")

	// Create map
	fruits := map[string]int{
		"apple":  5,
		"banana": 3,
	}
	fmt.Printf("Initial: %v\n", fruits)

	// Add new element
	fruits["cherry"] = 8
	fmt.Printf("After adding cherry: %v\n", fruits)

	// Update existing element
	fruits["apple"] = 10
	fmt.Printf("After updating apple: %v\n", fruits)

	// Add or update using function
	fruits["date"] = fruits["date"] + 1
	fmt.Printf("After add/update date: %v\n", fruits)
}

// 3. Accessing Elements

// AccessElementsExample demonstrates accessing map elements
func AccessElementsExample() {
	fmt.Println("\n--- Accessing Elements ---")

	scores := map[string]int{
		"Alice":   95,
		"Bob":     87,
		"Charlie": 92,
	}

	// Access existing key
	aliceScore := scores["Alice"]
	fmt.Printf("Alice's score: %d\n", aliceScore)

	// Access non-existing key (returns zero value)
	davidScore := scores["David"]
	fmt.Printf("David's score (zero value): %d\n", davidScore)

	// Check if key exists
	value, exists := scores["Bob"]
	if exists {
		fmt.Printf("Bob's score: %d\n", value)
	}

	value, exists = scores["Eve"]
	if !exists {
		fmt.Printf("Eve not found in map\n")
	}
}

// 4. Deleting Elements

// DeleteElementsExample demonstrates deleting map entries
func DeleteElementsExample() {
	fmt.Println("\n--- Deleting Elements ---")

	m := map[string]int{
		"one":   1,
		"two":   2,
		"three": 3,
		"four":  4,
	}
	fmt.Printf("Initial: %v\n", m)

	// Delete key
	delete(m, "two")
	fmt.Printf("After deleting 'two': %v\n", m)

	// Delete non-existing key (no error)
	delete(m, "five")
	fmt.Printf("After deleting 'five' (no error): %v\n", m)
}

// 5. Iterating Over Maps

// IterateMapsExample demonstrates map iteration
func IterateMapsExample() {
	fmt.Println("\n--- Iterating Over Maps ---")

	ages := map[string]int{
		"Alice":   30,
		"Bob":     25,
		"Charlie": 35,
	}

	// Iterate over key-value pairs
	fmt.Println("All entries:")
	for name, age := range ages {
		fmt.Printf("  %s: %d\n", name, age)
	}

	// Iterate over keys
	fmt.Println("\nAll names:")
	for name := range ages {
		fmt.Printf("  %s\n", name)
	}

	// Iterate over values
	fmt.Println("\nAll ages:")
	for _, age := range ages {
		fmt.Printf("  %d\n", age)
	}
}

// 6. Map Operations

// MapOperationsExample demonstrates common map operations
func MapOperationsExample() {
	fmt.Println("\n--- Map Operations ---")

	// Size
	m := map[string]int{
		"a": 1, "b": 2, "c": 3,
	}
	fmt.Printf("Map size: %d\n", len(m))

	// Check if empty
	isEmpty := len(m) == 0
	fmt.Printf("Is empty: %v\n", isEmpty)

	// Clear map (create new one)
	m = make(map[string]int)
	fmt.Printf("After clearing: %v (size=%d)\n", m, len(m))
}

// 7. Map with Struct Values

// MapWithStructExample demonstrates maps with struct values
func MapWithStructExample() {
	fmt.Println("\n--- Map with Struct Values ---")

	// Person struct
	type Person struct {
		Name string
		Age  int
		City string
	}

	// Map with struct values
	people := map[string]Person{
		"p1": {Name: "Alice", Age: 30, City: "NYC"},
		"p2": {Name: "Bob", Age: 25, City: "LA"},
	}

	// Access struct fields
	fmt.Printf("p1: %s, %d, %s\n",
		people["p1"].Name,
		people["p1"].Age,
		people["p1"].City)

	// Modify struct
	p := people["p2"]
	p.Age = 26
	people["p2"] = p
	fmt.Printf("Updated p2: %s, %d\n", people["p2"].Name, people["p2"].Age)
}

// 8. Nested Maps

// NestedMapExample demonstrates nested maps
func NestedMapExample() {
	fmt.Println("\n--- Nested Maps ---")

	// Map of maps
	departments := map[string]map[string]int{
		"Engineering": {
			"Alice": 30,
			"Bob":   25,
		},
		"Sales": {
			"Charlie": 35,
			"David":  28,
		},
	}

	// Access nested map
	engineers := departments["Engineering"]
	fmt.Printf("Engineering department: %v\n", engineers)

	// Add to nested map
	departments["Marketing"] = map[string]int{
		"Eve": 32,
	}
	fmt.Printf("All departments: %v\n", departments)
}

// 9. Map Keys and Values Slices

// KeysValuesExample demonstrates extracting keys and values
func KeysValuesExample() {
	fmt.Println("\n--- Extract Keys and Values ---")

	scores := map[string]int{
		"Alice":   95,
		"Bob":     87,
		"Charlie": 92,
	}

	// Get keys
	keys := make([]string, 0, len(scores))
	for key := range scores {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	fmt.Printf("Sorted keys: %v\n", keys)

	// Get values
	values := make([]int, 0, len(scores))
	for _, value := range scores {
		values = append(values, value)
	}
	sort.Ints(values)
	fmt.Printf("Sorted values: %v\n", values)
}

// 10. Map Filtering

// FilterMapExample demonstrates filtering map entries
func FilterMapExample() {
	fmt.Println("\n--- Filtering Maps ---")

	scores := map[string]int{
		"Alice":   95,
		"Bob":     67,
		"Charlie": 82,
		"David":   58,
		"Eve":     91,
	}

	// Filter high scores (>= 80)
	highScores := make(map[string]int)
	for name, score := range scores {
		if score >= 80 {
			highScores[name] = score
		}
	}
	fmt.Printf("High scores (>=80): %v\n", highScores)

	// Filter by name length
	shortNames := make(map[string]int)
	for name, score := range scores {
		if len(name) <= 4 {
			shortNames[name] = score
		}
	}
	fmt.Printf("Short names (<=4 chars): %v\n", shortNames)
}

// 11. Map Transformation

// TransformMapExample demonstrates map transformation
func TransformMapExample() {
	fmt.Println("\n--- Transforming Maps ---")

	prices := map[string]float64{
		"apple":  1.50,
		"banana": 0.75,
		"cherry": 2.00,
	}

	// Apply discount (10% off)
	discounted := make(map[string]float64)
	for item, price := range prices {
		discounted[item] = price * 0.9
	}
	fmt.Printf("Original prices: %v\n", prices)
	fmt.Printf("Discounted prices: %v\n", discounted)

	// Convert to uppercase keys
	upperKeys := make(map[string]float64)
	for item, price := range prices {
		upperKeys[strings.ToUpper(item)] = price
	}
	fmt.Printf("Uppercase keys: %v\n", upperKeys)
}

// 12. Map Comparison

// CompareMapsExample demonstrates comparing maps
func CompareMapsExample() {
	fmt.Println("\n--- Comparing Maps ---")

	map1 := map[string]int{
		"a": 1,
		"b": 2,
		"c": 3,
	}

	map2 := map[string]int{
		"a": 1,
		"b": 2,
		"c": 3,
	}

	map3 := map[string]int{
		"a": 1,
		"b": 2,
		"c": 4, // Different value
	}

	// Check equality
	equal := len(map1) == len(map2)
	if equal {
		for key, value := range map1 {
			if map2[key] != value {
				equal = false
				break
			}
		}
	}
	fmt.Printf("map1 == map2: %v\n", equal)

	equal = len(map1) == len(map3)
	if equal {
		for key, value := range map1 {
			if map3[key] != value {
				equal = false
				break
			}
		}
	}
	fmt.Printf("map1 == map3: %v\n", equal)
}

// 13. Map Merging

// MergeMapsExample demonstrates merging maps
func MergeMapsExample() {
	fmt.Println("\n--- Merging Maps ---")

	map1 := map[string]int{
		"a": 1,
		"b": 2,
	}

	map2 := map[string]int{
		"b": 3,  // Override
		"c": 4,
	}

	// Merge (map2 values override map1)
	merged := make(map[string]int)

	// Copy map1
	for key, value := range map1 {
		merged[key] = value
	}

	// Add/override with map2
	for key, value := range map2 {
		merged[key] = value
	}

	fmt.Printf("map1: %v\n", map1)
	fmt.Printf("map2: %v\n", map2)
	fmt.Printf("merged: %v\n", merged)
}

// 14. Counting with Maps

// CountWithMapExample demonstrates counting with maps
func CountWithMapExample() {
	fmt.Println("\n--- Counting with Maps ---")

	// Count word frequencies
	text := "apple banana apple cherry banana apple"
	words := strings.Split(text, " ")

	frequency := make(map[string]int)
	for _, word := range words {
		frequency[word]++
	}

	fmt.Println("Word frequencies:")
	for word, count := range frequency {
		fmt.Printf("  %s: %d\n", word, count)
	}

	// Group by parity
	numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	groups := make(map[string][]int)

	for _, num := range numbers {
		if num%2 == 0 {
			groups["even"] = append(groups["even"], num)
		} else {
			groups["odd"] = append(groups["odd"], num)
		}
	}

	fmt.Println("\nGroups by parity:")
	for group, nums := range groups {
		fmt.Printf("  %s: %v\n", group, nums)
	}
}

// 15. Map Utilities

// MapKeys returns all keys as a slice
func MapKeys(m map[string]int) []string {
	keys := make([]string, 0, len(m))
	for key := range m {
		keys = append(keys, key)
	}
	return keys
}

// MapValues returns all values as a slice
func MapValues(m map[string]int) []int {
	values := make([]int, 0, len(m))
	for _, value := range m {
		values = append(values, value)
	}
	return values
}

// CopyMap creates a shallow copy of map
func CopyMap(m map[string]int) map[string]int {
	copy := make(map[string]int)
	for key, value := range m {
		copy[key] = value
	}
	return copy
}

// MapUtilitiesExample demonstrates utility functions
func MapUtilitiesExample() {
	fmt.Println("\n--- Map Utilities ---")

	m := map[string]int{
		"apple":  5,
		"banana": 3,
		"cherry": 8,
	}

	fmt.Printf("Keys: %v\n", MapKeys(m))
	fmt.Printf("Values: %v\n", MapValues(m))

	m2 := CopyMap(m)
	m2["date"] = 10
	fmt.Printf("Original: %v\n", m)
	fmt.Printf("Copy: %v\n", m2)
}

// Main function
func main() {
	fmt.Println("=== Web Go Maps and Dictionaries Examples ===\n")

	CreateMapsExample()
	AddUpdateElementsExample()
	AccessElementsExample()
	DeleteElementsExample()
	IterateMapsExample()
	MapOperationsExample()
	MapWithStructExample()
	NestedMapExample()
	KeysValuesExample()
	FilterMapExample()
	TransformMapExample()
	CompareMapsExample()
	MergeMapsExample()
	CountWithMapExample()
	MapUtilitiesExample()

	fmt.Println("\n=== All Maps and Dictionaries Examples Completed ===")
}

// Web Go Trees and Graphs Examples
// Implementing tree and graph data structures

package main

import (
	"container/list"
	"fmt"
)

// 1. Binary Tree Node

// TreeNode represents a binary tree node
type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}

// NewTreeNode creates a new tree node
func NewTreeNode(value int) *TreeNode {
	return &TreeNode{Value: value}
}

// 2. Binary Tree Operations

// Insert inserts a value into the BST
func (n *TreeNode) Insert(value int) *TreeNode {
	if n == nil {
		return NewTreeNode(value)
	}

	if value < n.Value {
		n.Left = n.Left.Insert(value)
	} else {
		n.Right = n.Right.Insert(value)
	}

	return n
}

// Search searches for a value in the BST
func (n *TreeNode) Search(value int) bool {
	if n == nil {
		return false
	}

	if value == n.Value {
		return true
	}

	if value < n.Value {
		return n.Left.Search(value)
	}

	return n.Right.Search(value)
}

// FindMin finds minimum value in BST
func (n *TreeNode) FindMin() *TreeNode {
	current := n
	for current.Left != nil {
		current = current.Left
	}
	return current
}

// FindMax finds maximum value in BST
func (n *TreeNode) FindMax() *TreeNode {
	current := n
	for current.Right != nil {
		current = current.Right
	}
	return current
}

// 3. Tree Traversals

// InOrder traversal (Left, Root, Right)
func (n *TreeNode) InOrder() []int {
	result := []int{}
	n.inOrder(&result)
	return result
}

func (n *TreeNode) inOrder(result *[]int) {
	if n == nil {
		return
	}

	n.Left.inOrder(result)
	*result = append(*result, n.Value)
	n.Right.inOrder(result)
}

// PreOrder traversal (Root, Left, Right)
func (n *TreeNode) PreOrder() []int {
	result := []int{}
	n.preOrder(&result)
	return result
}

func (n *TreeNode) preOrder(result *[]int) {
	if n == nil {
		return
	}

	*result = append(*result, n.Value)
	n.Left.preOrder(result)
	n.Right.preOrder(result)
}

// PostOrder traversal (Left, Right, Root)
func (n *TreeNode) PostOrder() []int {
	result := []int{}
	n.postOrder(&result)
	return result
}

func (n *TreeNode) postOrder(result *[]int) {
	if n == nil {
		return
	}

	n.Left.postOrder(result)
	n.Right.postOrder(result)
	*result = append(*result, n.Value)
}

// LevelOrder traversal (BFS)
func (n *TreeNode) LevelOrder() []int {
	if n == nil {
		return []int{}
	}

	result := []int{}
	queue := []*TreeNode{n}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		result = append(result, current.Value)

		if current.Left != nil {
			queue = append(queue, current.Left)
		}
		if current.Right != nil {
			queue = append(queue, current.Right)
		}
	}

	return result
}

// 4. Tree Properties

// Height calculates tree height
func (n *TreeNode) Height() int {
	if n == nil {
		return 0
	}

	leftHeight := n.Left.Height()
	rightHeight := n.Right.Height()

	if leftHeight > rightHeight {
		return leftHeight + 1
	}
	return rightHeight + 1
}

// Size counts all nodes
func (n *TreeNode) Size() int {
	if n == nil {
		return 0
	}

	return 1 + n.Left.Size() + n.Right.Size()
}

// IsLeaf checks if node is leaf
func (n *TreeNode) IsLeaf() bool {
	return n.Left == nil && n.Right == nil
}

// CountLeaves counts leaf nodes
func (n *TreeNode) CountLeaves() int {
	if n == nil {
		return 0
	}

	if n.IsLeaf() {
		return 1
	}

	return n.Left.CountLeaves() + n.Right.CountLeaves()
}

// 5. Tree Examples

// BinaryTreeExample demonstrates binary tree operations
func BinaryTreeExample() {
	fmt.Println("--- Binary Tree Example ---")

	// Create BST
	root := NewTreeNode(50)
	root.Insert(30)
	root.Insert(70)
	root.Insert(20)
	root.Insert(40)
	root.Insert(60)
	root.Insert(80)

	fmt.Printf("Tree structure:\n")
	fmt.Printf("      50\n")
	fmt.Printf("    /   \\\n")
	fmt.Printf("  30      70\n")
	fmt.Printf(" /  \    /  \\\n")
	fmt.Printf("20  40  60  80\n\n")

	// Traversals
	fmt.Printf("InOrder: %v\n", root.InOrder())
	fmt.Printf("PreOrder: %v\n", root.PreOrder())
	fmt.Printf("PostOrder: %v\n", root.PostOrder())
	fmt.Printf("LevelOrder: %v\n", root.LevelOrder())

	// Properties
	fmt.Printf("Height: %d\n", root.Height())
	fmt.Printf("Size: %d\n", root.Size())
	fmt.Printf("Leaves: %d\n", root.CountLeaves())

	// Search
	fmt.Printf("Search 40: %v\n", root.Search(40))
	fmt.Printf("Search 45: %v\n", root.Search(45))

	// Min/Max
	minNode := root.FindMin()
	maxNode := root.FindMax()
	fmt.Printf("Min: %d\n", minNode.Value)
	fmt.Printf("Max: %d\n", maxNode.Value)
}

// 6. Graph Implementation

// Graph represents an adjacency list graph
type Graph struct {
	vertices map[string][]string
	directed bool
}

// NewGraph creates a new graph
func NewGraph(directed bool) *Graph {
	return &Graph{
		vertices: make(map[string][]string),
		directed: directed,
	}
}

// AddVertex adds a vertex
func (g *Graph) AddVertex(vertex string) {
	if _, exists := g.vertices[vertex]; !exists {
		g.vertices[vertex] = []string{}
	}
}

// AddEdge adds an edge between vertices
func (g *Graph) AddEdge(from, to string) {
	if _, exists := g.vertices[from]; !exists {
		g.AddVertex(from)
	}
	if _, exists := g.vertices[to]; !exists {
		g.AddVertex(to)
	}

	g.vertices[from] = append(g.vertices[from], to)

	if !g.directed {
		g.vertices[to] = append(g.vertices[to], from)
	}
}

// GetVertices returns all vertices
func (g *Graph) GetVertices() []string {
	vertices := make([]string, 0, len(g.vertices))
	for v := range g.vertices {
		vertices = append(vertices, v)
	}
	return vertices
}

// GetNeighbors returns neighbors of a vertex
func (g *Graph) GetNeighbors(vertex string) []string {
	if neighbors, exists := g.vertices[vertex]; exists {
		return neighbors
	}
	return []string{}
}

// 7. Graph Traversals

// BFS performs breadth-first search
func (g *Graph) BFS(start string) []string {
	visited := make(map[string]bool)
	queue := []string{start}
	result := []string{}

	visited[start] = true

	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]

		result = append(result, vertex)

		for _, neighbor := range g.GetNeighbors(vertex) {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}

	return result
}

// DFS performs depth-first search (iterative)
func (g *Graph) DFS(start string) []string {
	visited := make(map[string]bool)
	stack := []string{start}
	result := []string{}

	for len(stack) > 0 {
		// Pop from stack
		vertex := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if !visited[vertex] {
			visited[vertex] = true
			result = append(result, vertex)

			// Add neighbors in reverse order
			neighbors := g.GetNeighbors(vertex)
			for i := len(neighbors) - 1; i >= 0; i-- {
				if !visited[neighbors[i]] {
					stack = append(stack, neighbors[i])
				}
			}
		}
	}

	return result
}

// DFSRecursive performs recursive DFS
func (g *Graph) DFSRecursive(start string) []string {
	visited := make(map[string]bool)
	result := []string{}
	g.dfsRecursiveHelper(start, visited, &result)
	return result
}

func (g *Graph) dfsRecursiveHelper(vertex string, visited map[string]bool, result *[]string) {
	visited[vertex] = true
	*result = append(*result, vertex)

	for _, neighbor := range g.GetNeighbors(vertex) {
		if !visited[neighbor] {
			g.dfsRecursiveHelper(neighbor, visited, result)
		}
	}
}

// 8. Graph Algorithms

// HasPath checks if there's a path from start to end
func (g *Graph) HasPath(start, end string) bool {
	visited := make(map[string]bool)
	queue := []string{start}
	visited[start] = true

	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]

		if vertex == end {
			return true
		}

		for _, neighbor := range g.GetNeighbors(vertex) {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}

	return false
}

// ShortestPath finds shortest path using BFS
func (g *Graph) ShortestPath(start, end string) []string {
	if start == end {
		return []string{start}
	}

	// BFS with parent tracking
	parent := make(map[string]string)
	visited := make(map[string]bool)
	queue := []string{start}

	visited[start] = true

	found := false
	for len(queue) > 0 {
		vertex := queue[0]
		queue = queue[1:]

		for _, neighbor := range g.GetNeighbors(vertex) {
			if !visited[neighbor] {
				visited[neighbor] = true
				parent[neighbor] = vertex
				queue = append(queue, neighbor)

				if neighbor == end {
					found = true
					break
				}
			}
		}

		if found {
			break
		}
	}

	if !found {
		return []string{}
	}

	// Reconstruct path
	path := []string{end}
	current := end
	for current != start {
		current = parent[current]
		path = append([]string{current}, path...)
	}

	return path
}

// GraphExample demonstrates graph operations
func GraphExample() {
	fmt.Println("\n--- Graph Example ---")

	// Create undirected graph
	g := NewGraph(false)

	// Add edges
	g.AddEdge("A", "B")
	g.AddEdge("A", "C")
	g.AddEdge("B", "D")
	g.AddEdge("C", "D")
	g.AddEdge("D", "E")

	fmt.Println("Graph structure:")
	fmt.Println("  A -- B")
	fmt.Println("  |    |")
	fmt.Println("  C -- D -- E")

	fmt.Printf("\nVertices: %v\n", g.GetVertices())

	// Traversals
	fmt.Printf("BFS from A: %v\n", g.BFS("A"))
	fmt.Printf("DFS from A: %v\n", g.DFS("A"))
	fmt.Printf("DFS Recursive from A: %v\n", g.DFSRecursive("A"))

	// Path finding
	fmt.Printf("Has path A->E: %v\n", g.HasPath("A", "E"))
	fmt.Printf("Shortest path A->E: %v\n", g.ShortestPath("A", "E"))
}

// 9. N-ary Tree

// NAryNode represents an n-ary tree node
type NAryNode struct {
	Value     string
	Children  []*NAryNode
}

// NewNAryNode creates a new n-ary node
func NewNAryNode(value string) *NAryNode {
	return &NAryNode{
		Value:    value,
		Children: []*NAryNode{},
	}
}

// AddChild adds a child node
func (n *NAryNode) AddChild(child *NAryNode) {
	n.Children = append(n.Children, child)
}

// LevelOrderNAry performs level-order traversal for n-ary tree
func (n *NAryNode) LevelOrderNAry() []string {
	if n == nil {
		return []string{}
	}

	result := []string{}
	queue := []*NAryNode{n}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		result = append(result, current.Value)

		for _, child := range current.Children {
			queue = append(queue, child)
		}
	}

	return result
}

// NAryTreeExample demonstrates n-ary tree
func NAryTreeExample() {
	fmt.Println("\n--- N-ary Tree Example ---")

	root := NewNAryNode("Root")
	child1 := NewNAryNode("Child1")
	child2 := NewNAryNode("Child2")
	child3 := NewNAryNode("Child3")

	root.AddChild(child1)
	root.AddChild(child2)
	root.AddChild(child3)

	child1.AddChild(NewNAryNode("Grandchild1"))
	child1.AddChild(NewNAryNode("Grandchild2"))

	child2.AddChild(NewNAryNode("Grandchild3"))

	fmt.Println("N-ary Tree structure:")
	fmt.Println("        Root")
	fmt.Println("       / | \\")
	fmt.Println("     c1  c2  c3")
	fmt.Println("    /  \    \")
	fmt.Println("  gc1  gc2  gc3")

	fmt.Printf("\nLevelOrder: %v\n", root.LevelOrderNAry())
}

// 10. Trie (Prefix Tree)

// TrieNode represents a trie node
type TrieNode struct {
	Children map[rune]*TrieNode
	IsEnd    bool
}

// NewTrieNode creates a new trie node
func NewTrieNode() *TrieNode {
	return &TrieNode{
		Children: make(map[rune]*TrieNode),
		IsEnd:    false,
	}
}

// Trie represents a trie
type Trie struct {
	Root *TrieNode
}

// NewTrie creates a new trie
func NewTrie() *Trie {
	return &Trie{Root: NewTrieNode()}
}

// Insert inserts a word into the trie
func (t *Trie) Insert(word string) {
	node := t.Root

	for _, char := range word {
		if _, exists := node.Children[char]; !exists {
			node.Children[char] = NewTrieNode()
		}
		node = node.Children[char]
	}

	node.IsEnd = true
}

// Search searches for a word in the trie
func (t *Trie) Search(word string) bool {
	node := t.Root

	for _, char := range word {
		if _, exists := node.Children[char]; !exists {
			return false
		}
		node = node.Children[char]
	}

	return node.IsEnd
}

// StartsWith checks if any word starts with prefix
func (t *Trie) StartsWith(prefix string) bool {
	node := t.Root

	for _, char := range prefix {
		if _, exists := node.Children[char]; !exists {
			return false
		}
		node = node.Children[char]
	}

	return true
}

// TrieExample demonstrates trie operations
func TrieExample() {
	fmt.Println("\n--- Trie Example ---")

	trie := NewTrie()

	// Insert words
	words := []string{"apple", "app", "application", "banana"}
	for _, word := range words {
		trie.Insert(word)
		fmt.Printf("Inserted: %s\n", word)
	}

	// Search
	fmt.Printf("\nSearch 'app': %v\n", trie.Search("app"))
	fmt.Printf("Search 'apple': %v\n", trie.Search("apple"))
	fmt.Printf("Search 'apples': %v\n", trie.Search("apples"))

	// StartsWith
	fmt.Printf("\nStartsWith 'app': %v\n", trie.StartsWith("app"))
	fmt.Printf("StartsWith 'ban': %v\n", trie.StartsWith("ban"))
	fmt.Printf("StartsWith 'orange': %v\n", trie.StartsWith("orange"))
}

// Main function
func main() {
	fmt.Println("=== Web Go Trees and Graphs Examples ===\n")

	BinaryTreeExample()
	GraphExample()
	NAryTreeExample()
	TrieExample()

	fmt.Println("\n=== All Trees and Graphs Examples Completed ===")
}