Qual é a diferença entre profundidade e altura da árvore?

Esta é uma pergunta simples da teoria dos algoritmos.
A diferença entre eles é que, em um caso, você conta o número de nós e em outro número de arestas no caminho mais curto entre o nó raiz e o concreto.
Qual e qual?

Aprendi que profundidade e altura são propriedades de um nó :

• A profundidade de um nó é o número de arestas do nó até o nó raiz da árvore.
  Um nó raiz terá uma profundidade de 0.

• A altura de um nó é o número de arestas no caminho mais longo do nó para uma folha.
  Um nó folha terá uma altura de 0.

Propriedades de uma árvore :

• A altura de uma árvore seria a altura do nó raiz
  ou, equivalentemente, a profundidade do nó mais profundo.

• O diâmetro (ou largura ) de uma árvore é o número de nós no caminho mais longo entre dois nós de folhas. A árvore abaixo tem um diâmetro de 6 nós.

a altura e a profundidade de uma árvore são iguais ...

mas a altura e a profundidade de um nó não são iguais porque ...

a altura é calculada atravessando o nó especificado para a folha mais profunda possível.

a profundidade é calculada a partir da passagem da raiz para o nó especificado .....

De acordo com Cormen et al. Introdução aos algoritmos (Apêndice B.5.3), a profundidade de um nó X em uma árvore T é definida como o comprimento do caminho simples (número de arestas) do nó raiz de T a X. A altura de um nó Y é o número de arestas no caminho simples descendente mais longo, de Y a uma folha. A altura de uma árvore é definida como a altura do seu nó raiz.

Observe que um caminho simples é um caminho sem vértices repetidos.

A altura de uma árvore é igual à profundidade máxima de uma árvore . A profundidade de um nó e a altura de um nó não são necessariamente iguais. Veja a Figura B.6 da 3ª Edição de Cormen et al. para uma ilustração desses conceitos.

Às vezes, tenho visto problemas em solicitar que se conte nós (vértices) em vez de arestas; portanto, peça esclarecimentos se não tiver certeza de que deve contar nós ou arestas durante um exame ou uma entrevista de emprego.

Resposta Simples:
Profundidade:
1. Árvore : O número de arestas / arco do nó raiz ao nó folha da árvore é chamado de Profundidade da Árvore.
2. Nó : O número de arestas / arco do nó raiz para esse nó é chamado como Profundidade desse nó.

Outra maneira de entender esses conceitos é a seguinte: Profundidade: desenhe uma linha horizontal na posição raiz e trate essa linha como terra. Portanto, a profundidade da raiz é 0 e todos os seus filhos crescem para baixo, para que cada nível de nós tenha a profundidade atual + 1.

Altura: a mesma linha horizontal, mas desta vez a posição do solo são nós externos, que são a folha da árvore e contam para cima.

Eu queria fazer este post porque sou um estudante de graduação em CS e cada vez mais usamos o OpenDSA e outros livros de código aberto. Parece que, a partir da resposta mais bem avaliada, a maneira como a altura e a profundidade estão sendo ensinadas mudou de uma geração para a seguinte, e eu estou postando isso para que todos saibam que essa discrepância agora existe e, esperamos, não cause bugs em nenhuma programas! Obrigado.

Do livro OpenDSA Data Structures & Algos :

Se n ₁ , n ₂ , ..., n _k é uma sequência de nós na árvore, de modo que n _i é o pai de n _i +1 para 1 <= i <k, essa sequência é chamada de caminho de n ₁ a n _k . O comprimento do caminho é k-1. Se houver um caminho do nó R para o nó M, então R é um ancestral de M e M é um descendente de R. Portanto, todos os nós da árvore são descendentes da raiz da árvore, enquanto a raiz é o ancestral de todos os nós. A profundidade de um nó M na árvore é o comprimento do caminho desde a raiz da árvore até M. A altura de uma árvore é um a mais que a profundidade do nó mais profundo da árvore.Todos os nós de profundidade d estão no nível d na árvore. A raiz é o único nó no nível 0 e sua profundidade é 0.

Figura 7.2.1: Uma árvore binária. O nó A é a raiz. Os nós B e C são filhos de A. Os nós B e D juntos formam uma subárvore. O nó B tem dois filhos: o filho esquerdo é a árvore vazia e o filho direito é D. Os nós A, C e E são ancestrais de G. Os nós D, E e F compõem o nível 2 da árvore; o nó A está no nível 0. As arestas de A a C a E a G formam um caminho de comprimento 3. Os nós D, G, H e I são folhas. Os nós A, B, C, E e F são nós internos. A profundidade de I é 3. A altura desta árvore é 4.