Data Structure & Algorithms
Trees: terminología, DFS y BFS
Terminología de árboles, formas y alturas, recorridos DFS preorder, inorder y postorder, BFS por niveles y análisis según altura o ancho.
- Última actualización
- Actualizada
- Nivel
- Fundamentos
Data Structure & Algorithms
Terminología de árboles, formas y alturas, recorridos DFS preorder, inorder y postorder, BFS por niveles y análisis según altura o ancho.
Un tree organiza datos mediante relaciones padre-hijo. Tiene una raíz y cada nodo, salvo la raíz, tiene exactamente un padre.
Un árbol es un grafo conectado y sin ciclos. Esa propiedad permite recorrerlo sin un conjunto visited cuando las referencias solo van de padre a hijos. Si el modelo también guarda el padre o conexiones generales, debes evitar regresar por donde llegaste.
A raíz
/ \
B C hijos de A
/ \ \
D E F hojas: D, E, FAlgunas fuentes cuentan altura en nodos y otras en aristas. Define la convención antes de comparar resultados. Aquí un árbol de un solo nodo tiene altura 0; el árbol vacío puede definirse como -1 para facilitar recurrencias.
En un binary tree cada nodo tiene como máximo dos hijos: left y right.
type BinaryNode<T> = {
value: T;
left: BinaryNode<T> | null;
right: BinaryNode<T> | null;
};“Binary” describe la cantidad de hijos. No implica orden. Un BST añade un invariante de búsqueda; un heap añade una prioridad entre padres e hijos.
O(log n) según la definición de la estructura.O(n).Estas propiedades no son sinónimos.
Depth-First Search cambia según cuándo procesas el nodo.
Procesa el nodo antes de sus subárboles.
A → B → D → E → C → FÚtil para:
function preorder<T>(root: BinaryNode<T> | null): T[] {
if (!root) return [];
const result: T[] = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop()!;
result.push(node.value);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}Se inserta primero right porque el stack es LIFO y queremos procesar left antes.
D → B → E → A → C → FEn un binary tree normal es solo un orden. En un BST produce las claves ordenadas.
function inorder<T>(root: BinaryNode<T> | null): T[] {
const result: T[] = [];
const stack: BinaryNode<T>[] = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop()!;
result.push(current.value);
current = current.right;
}
return result;
}D → E → B → F → C → AProcesa los hijos antes del padre. Es natural para:
function height<T>(node: BinaryNode<T> | null): number {
if (!node) return -1;
return 1 + Math.max(height(node.left), height(node.right));
}La recurrencia expresa que la altura depende de la mayor altura de sus hijos.
Los tres traversals visitan cada nodo una vez:
O(n);O(h) por stack explícito o call stack.En un árbol balanceado, h = O(log n). En uno degenerado, h = O(n). Decir espacio O(log n) sin conocer la forma es incorrecto.
BFS procesa el árbol por niveles.
nivel 0: A
nivel 1: B, C
nivel 2: D, E, Ffunction levelOrder<T>(root: BinaryNode<T> | null): T[][] {
if (!root) return [];
const levels: T[][] = [];
const queue = [root];
let head = 0;
while (head < queue.length) {
const levelSize = queue.length - head;
const level: T[] = [];
for (let i = 0; i < levelSize; i += 1) {
const node = queue[head];
head += 1;
level.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
levels.push(level);
}
return levels;
}levelSize se captura antes de agregar hijos; representa exactamente los nodos del nivel actual.
Tiempo: O(n). Memoria adicional: O(w), donde w es el ancho máximo. En un árbol perfecto, el último nivel puede contener cerca de n/2 nodos, por lo que el peor caso es O(n).
| Necesidad | Traversal | Razón |
|---|---|---|
| Procesar padre antes que hijos | Preorder | El contexto baja |
| Claves ordenadas en BST | Inorder | Respeta izquierda-nodo-derecha |
| Combinar información de hijos | Postorder | Los resultados suben |
| Procesar niveles | BFS | La cola conserva distancia desde la raíz |
| Primer nodo a cierta profundidad | BFS | Explora por capas |
| Rutas raíz-hoja | DFS | Mantiene un camino activo |
No elijas por costumbre. El orden en que necesitas información determina el traversal.
function rootToLeafPaths<T>(root: BinaryNode<T> | null): T[][] {
const result: T[][] = [];
const path: T[] = [];
function visit(node: BinaryNode<T> | null): void {
if (!node) return;
path.push(node.value);
if (!node.left && !node.right) {
result.push([...path]);
} else {
visit(node.left);
visit(node.right);
}
path.pop();
}
visit(root);
return result;
}Invariante: path contiene exactamente los valores desde la raíz hasta el nodo actual. El pop restaura el estado antes de explorar otra rama.
Un nodo puede tener cualquier cantidad de hijos:
type TreeNode<T> = {
value: T;
children: TreeNode<T>[];
};DFS y BFS siguen siendo válidos. Cambia el loop sobre hijos, no el modelo del traversal.
Ejemplos reales:
Un árbol es:
vacío
o
nodo + lista de subárbolesPor eso la recursión expresa muchos algoritmos con naturalidad. Sin embargo, “natural” no significa segura para cualquier profundidad. JavaScript no garantiza tail-call optimization práctica y un árbol degenerado grande puede desbordar el call stack.
shift() en BFS.O(log n) para cualquier árbol.queue.length mientras cambia sin fijar levelSize.path en resultados sin copiarlo.O(n); espacio depende de altura o ancho.¿Por qué postorder es adecuado para comprobar si un árbol está balanceado?
Porque la decisión en un nodo depende de conocer primero la altura y el balance de ambos hijos. Postorder calcula esa información antes de procesar al padre.