¿Cuál es la diferencia entre la profundidad y la altura del árbol?

Esta es una pregunta simple de la teoría de algoritmos.
La diferencia entre ellos es que, en un caso, cuenta el número de nodos y en el otro número de bordes en la ruta más corta entre el nodo raíz y el nodo concreto.
¿Cual es cual?

Aprendí que la profundidad y la altura son propiedades de un nodo :

• los profundidad de un nodo es el número de aristas desde el nodo hasta el nodo raíz del árbol.
  Un nodo raíz tendrá una profundidad de 0.

• La altura de un nodo es el número de aristas en la ruta más larga desde el nodo hasta una hoja.
  Un nodo hoja tendrá una altura de 0.

Propiedades de un árbol :

• La altura de un árbol sería la altura de su nodo raíz,
  o equivalente, la profundidad de su nodo más profundo.

• El diámetro (o ancho ) de un árbol es el número de nodos en la ruta más larga entre dos nodos de hoja. El árbol de abajo tiene un diámetro de 6 nodos.

la altura y la profundidad de un árbol es igual ...

pero la altura y la profundidad de un nodo no son iguales porque ...

la altura se calcula atravesando desde el nodo dado hasta la hoja más profunda posible.

la profundidad se calcula a partir del recorrido desde la raíz hasta el nodo dado .....

De acuerdo con Cormen et al. Introducción a los algoritmos (Apéndice B.5.3), la profundidad de un nodo X en un árbol T se define como la longitud de la ruta simple (número de aristas) desde el nodo raíz de T a X. La altura de un nodo Y es el número de bordes en el más largo camino simple descendente desde Y hasta una hoja. La altura de un árbol se define como la altura de su nodo raíz.

Tenga en cuenta que una ruta simple es una ruta sin vértices repetidos.

La altura de un árbol es igual a la profundidad máxima de un árbol . La profundidad de un nodo y la altura de un nodo no son necesariamente iguales. Ver Figura B.6 de la 3ra Edición de Cormen et al. para una ilustración de estos conceptos.

A veces he visto problemas pidiéndole a uno que cuente nodos (vértices) en lugar de bordes, así que solicite una aclaración si no está seguro de que debe contar nodos o bordes durante un examen o una entrevista de trabajo.

Respuesta simple:
Profundidad:
1. Árbol : el número de aristas / arco desde el nodo raíz hasta el nodo hoja del árbol se denomina Profundidad del árbol.
2. Nodo : el número de aristas / arco desde el nodo raíz hasta ese nodo se llama Profundidad de ese nodo.

Otra forma de entender esos conceptos es la siguiente: Profundidad: dibuje una línea horizontal en la posición raíz y trate esta línea como tierra. Por lo tanto, la profundidad de la raíz es 0, y todos sus hijos crecen hacia abajo, por lo que cada nivel de nodos tiene la profundidad actual + 1.

Altura: la misma línea horizontal pero esta vez la posición del suelo son nodos externos, que son la hoja del árbol y cuentan hacia arriba.

Quería hacer esta publicación porque soy un estudiante universitario de CS y cada vez más usamos OpenDSA y otros libros de texto de código abierto. Parece que, según la respuesta mejor calificada, la forma en que se enseña la altura y la profundidad ha cambiado de una generación a la siguiente, y estoy publicando esto para que todos sepan que esta discrepancia ahora existe y es de esperar que no cause errores en ninguna programas! Gracias.

Del libro OpenDSA Data Structures & Algos :

Si n ₁ , n ₂ , ..., n _k es una secuencia de nodos en el árbol de modo que n _i es el padre de n _i +1 para 1 <= i <k, entonces esta secuencia se llama ruta desde n ₁ to n _k . La longitud del camino es k − 1. Si hay una ruta desde el nodo R al nodo M, entonces R es un ancestro de M y M es un descendiente de R. Por lo tanto, todos los nodos en el árbol son descendientes de la raíz del árbol, mientras que la raíz es el ancestro de todos los nodos La profundidad de un nodo M en el árbol es la longitud del camino desde la raíz del árbol hasta M. La altura de un árbol es uno más que la profundidad del nodo más profundo del árbol.Todos los nodos de profundidad d están en el nivel d en el árbol. La raíz es el único nodo en el nivel 0, y su profundidad es 0.

Figura 7.2.1: Un árbol binario. El nodo A es la raíz. Los nodos B y C son hijos de A. Los nodos B y D juntos forman un subárbol. El nodo B tiene dos hijos: su hijo izquierdo es el árbol vacío y su hijo derecho es D. Los nodos A, C y E son ancestros de G. Los nodos D, E y F constituyen el nivel 2 del árbol; el nodo A está en el nivel 0. Los bordes de A a C a E a G forman una trayectoria de longitud 3. Los nodos D, G, H e I son hojas. Los nodos A, B, C, E y F son nodos internos. La profundidad de I es 3. La altura de este árbol es 4.