¿Cómo funciona la búsqueda en el árbol?

La búsqueda en un árbol depende de su estructura y del objetivo de la búsqueda.

Formas principales de búsqueda:

Búsqueda en profundidad (DFS - Depth-First Search): Se adentra lo más profundo posible en una rama antes de pasar a la siguiente. Se implementa usando una pila (explícita o implícitamente mediante recursión).
- Recorrido previo (Pre-order): Visitar la raíz, luego el subárbol izquierdo, luego el subárbol derecho.
- Recorrido en orden (In-order): Visitar el subárbol izquierdo, luego la raíz, luego el subárbol derecho. Se usa en árboles binarios de búsqueda para obtener una lista ordenada de elementos.
- Recorrido post-orden (Post-order): Visitar el subárbol izquierdo, luego el derecho, luego la raíz.
Búsqueda en anchura (BFS - Breadth-First Search): Explora todos los vecinos del nodo actual en un nivel antes de pasar al siguiente nivel. Se implementa usando una cola.

Ejemplo de DFS (In-order) para un árbol binario:

// TreeNode representa un nodo de árbol binario
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal realiza un recorrido inorder
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Llamada recursiva para el subárbol izquierdo
	result = append(result, InOrderTraversal(root.Left)...)
	// Visitar el nodo actual
	result = append(result, root.Val)
	// Llamada recursiva para el subárbol derecho
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Ejemplo de BFS:

// TreeNode representa un nodo de árbol binario
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal realiza un recorrido BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Cola para almacenar nodos en el nivel actual
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Extraer el primer elemento de la cola
		node := queue[0]
		queue = queue[1:]

		// Añadir el valor del nodo a los resultados
		result = append(result, node.Val)

		// Añadir el hijo izquierdo a la cola si existe
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Añadir el hijo derecho a la cola si existe
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Para árboles binarios de búsqueda (BST), donde el subárbol izquierdo es menor que la raíz y el derecho es mayor:

Búsqueda binaria: Al buscar un valor específico, se compara con la raíz. Si el valor es menor, se busca en el subárbol izquierdo; si es mayor, en el derecho. Es la estrategia más eficiente para buscar en BST.

// TreeNode representa un nodo de árbol binario de búsqueda
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST realiza una búsqueda binaria en un BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Nodo encontrado o árbol vacío
	}

	if target < root.Val {
		// Buscar en el subárbol izquierdo
		return SearchBST(root.Left, target)
	}
	// Buscar en el subárbol derecho
	return SearchBST(root.Right, target)
}

La elección del algoritmo de búsqueda depende de la tarea y las características del árbol. DFS es adecuado para tareas donde se necesita profundizar en una rama o encontrar un camino hacia un objetivo. BFS es útil para encontrar el camino más corto o recorrer por niveles. La búsqueda binaria es eficiente para encontrar un valor específico en estructuras ordenadas como BST.