# TDA | Practica 2 ejercicio 6 ## Consigna - Dado un árbol binario cualquiera, diseñar un algoritmo de dividir y conquistar que devuelva **la máxima distancia entre dos nodos** (es decir, máxima cantidad de ejes a atravesar). El algoritmo no debe hacer recorridos innecesarios sobre el árbol. - Hint: para saber el camino más largo de un árbol, posiblemente necesite conocer más que sólo los caminos más largos de sus subárboles. ## Resolución: - Para calcular la maxima distancia de 2 nodos hay que tener en cuenta: - La maxima distancia puede estar en el subarbol izquierdo - la max distancia puede esta en el subarbol derecho - está uno y uno. - Por lo tanto para cada nodo de manera recursiva habría que calcular: - La altura que sería la suma de las alturas de los subarboles izquierdo + derecho + los 2 bordes. - La distancia maxima dentro del arbol. - También habría que hacer un algoritmo de busqueda en profundidad. ```python class Nodo: def __init__(self, value=0, izquierda=None, derecha=None): self.value = value self.izquierda = izquierda self.derecha = derecha def distanciaMaxima(root): def dfs(nodo): if not nodo: return 0, 0 # tupla (altura, distancia máxima) # Parte de dividir: Recorrer los subárboles alturaIzquierda, maxDistanciaIzquierda = dfs(nodo.izquierda) alturaDerecha, maxDistanciaDerecha = dfs(nodo.derecha) # Parte de conquistar: Calcular la altura actual y la distancia actual alturaActual = max(alturaIzquierda, alturaDerecha) + 1 distanciaActual = alturaIzquierda + alturaDerecha + 1 # Parte de combinar: Actualizar la distancia máxima distanciaMaximaSubarboles = max(distanciaActual, maxDistanciaIzquierda , maxDistanciaDerecha) return alturaActual, distanciaMaximaSubarboles altura, distanciaMaxima = dfs(root) return distanciaMaxima ```