Dado un árbol binario, la tarea es encontrar la altura del árbol. La altura del árbol es el número de vértices del árbol desde la raíz hasta el nodo más profundo.

Nota: La altura de un árbol vacío es 0 y la altura de un árbol con un solo nodo es 1 .

Ejemplo de árbol binario

Calcular recursivamente la altura del izquierda y el bien subárboles de un nodo y asignar altura al nodo como máximo de las alturas de dos niños más 1 . Consulte a continuación el pseudocódigo y el programa para obtener más detalles.

Ilustración:

son ejemplos de modelos

Considere el siguiente árbol:

Ejemplo de árbol

profundidadmax('1') = max(profundidadmax('2'), profundidadmax('3')) + 1 = 2 + 1

porque recursivamente
maxDepth('2') = max (maxDepth('4'), maxDepth('5')) + 1 = 1 + 1 y (ya que la altura de '4' y '5' es 1)
profundidad máxima('3') = 1

Siga los pasos a continuación para implementar la idea:

• Realice de forma recursiva una búsqueda en profundidad.
• Si el árbol está vacío entonces devuelve 0
• De lo contrario, haga lo siguiente
  • Obtenga la profundidad máxima del subárbol izquierdo de forma recursiva, es decir, llame a maxDepth(árbol->subárbol izquierdo)
  • Obtenga la profundidad máxima del subárbol derecho de forma recursiva, es decir, llame a maxDepth(árbol->subárbol derecho)
  • Obtenga el máximo de profundidades máximas de izquierda y bien subárboles y agregar 1 a él para el nodo actual.
    • 
• Devuelve profundidad_max.

A continuación se muestra la implementación del enfoque anterior:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

JavaScript

>

>

Height of tree is 3>

Complejidad del tiempo: O(N) (Consulte la publicación en Recorrido del árbol para detalles)
Espacio Auxiliar: O(N) debido a la pila recursiva.

Encuentre la profundidad o altura máxima de un árbol usando Recorrido de orden de nivel :

Hacer Recorrido de orden de nivel , mientras agrega nodos en cada nivel para Siga los pasos a continuación para implementar la idea:

• Atraviese el árbol en orden de nivel a partir de raíz .
  • Inicializar una cola vacía q , una variable profundidad y empujar raíz , luego presione nulo en el q .
  • Ejecute un bucle while hasta q no está vacío.
    • Guarde el elemento frontal de q y saca el elemento frontal.
    • Si el frente de q es NULO luego incrementar profundidad por uno y si la cola no está vacía, presione NULO en el q .
    • De lo contrario, si el elemento no es NULO luego verifique su izquierda y bien niños y si no lo son NULO empujarlos hacia q .
• Devolver profundidad .

A continuación se muestra la implementación del enfoque anterior:

C++

#include> #include> using> namespace> std;> // A Tree node> struct> Node {> >int> key;> >struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->clave = clave;> >temp->izquierda = temp->derecha = NULL;> >return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(>struct> Node* root)> {> >// Initialising a variable to count the> >// height of tree> >int> depth = 0;> >queue q;> >// Pushing first level element along with NULL> >q.push(root);> >q.push(NULL);> >while> (!q.empty()) {> >Node* temp = q.front();> >q.pop();> >// When NULL encountered, increment the value> >if> (temp == NULL) {> >depth++;> >}> >// If NULL not encountered, keep moving> >if> (temp != NULL) {> >if> (temp->izquierda) {> >q.push(temp->izquierda);> >}> >if> (temp->derecha) {> >q.push(temp->derecha);> >}> >}> >// If queue still have elements left,> >// push NULL again to the queue.> >else> if> (!q.empty()) {> >q.push(NULL);> >}> >}> >return> depth;> }> // Driver program> int> main()> {> >// Let us create Binary Tree shown in above example> >Node* root = newNode(1);> >root->izquierda = nuevoNodo(2);> >root->derecha = nuevoNodo(3);> >root->izquierda->izquierda = nuevoNodo(4);> >root->izquierda->derecha = nuevoNodo(5);> >cout <<>'Height(Depth) of tree is: '> << height(root);> }>

>

>

Java

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> >// A tree node structure> >static> class> Node {> >int> key;> >Node left;> >Node right;> >}> >// Utility function to create> >// a new node> >static> Node newNode(>int> key)> >{> >Node temp =>new> Node();> >temp.key = key;> >temp.left = temp.right =>null>;> >return> temp;> >}> >/*Function to find the height(depth) of the tree*/> >public> static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >int> depth =>0>;> >Queue q =>new> LinkedList();> >// Pushing first level element along with null> >q.add(root);> >q.add(>null>);> >while> (!q.isEmpty()) {> >Node temp = q.peek();> >q.remove();> >// When null encountered, increment the value> >if> (temp ==>null>) {> >depth++;> >}> >// If null not encountered, keep moving> >if> (temp !=>null>) {> >if> (temp.left !=>null>) {> >q.add(temp.left);> >}> >if> (temp.right !=>null>) {> >q.add(temp.right);> >}> >}> >// If queue still have elements left,> >// push null again to the queue.> >else> if> (!q.isEmpty()) {> >q.add(>null>);> >}> >}> >return> depth;> >}> >// Driver Code> >public> static> void> main(String args[])> >{> >Node root = newNode(>1>);> >root.left = newNode(>2>);> >root.right = newNode(>3>);> >root.left.left = newNode(>4>);> >root.left.right = newNode(>5>);> >System.out.println(>'Height(Depth) of tree is: '> >+ height(root));> >}> }> // This code is contributed by jana_sayantan.>

>

>

Python3

# Python code to implement the approach> # A Tree node> class> Node:> >def> __init__(>self>):> >self>.key>=> 0> >self>.left,>self>.right>=> None>,>None> # Utility function to create a new node> def> newNode(key):> >temp>=> Node()> >temp.key>=> key> >temp.left, temp.right>=> None>,>None> >return> temp> # Function to find the height(depth) of the tree> def> height(root):> ># Initialising a variable to count the> ># height of tree> >depth>=> 0> >q>=> []> ># appending first level element along with None> >q.append(root)> >q.append(>None>)> >while>(>len>(q)>>0>):> >temp>=> q[>0>]> >q>=> q[>1>:]> ># When None encountered, increment the value> >if>(temp>=>=> None>):> >depth>+>=> 1> ># If None not encountered, keep moving> >if>(temp !>=> None>):> >if>(temp.left):> >q.append(temp.left)> >if>(temp.right):> >q.append(temp.right)> ># If queue still have elements left,> ># append None again to the queue.> >elif>(>len>(q)>>0>):> >q.append(>None>)> >return> depth> # Driver program> # Let us create Binary Tree shown in above example> root>=> newNode(>1>)> root.left>=> newNode(>2>)> root.right>=> newNode(>3>)> root.left.left>=> newNode(>4>)> root.left.right>=> newNode(>5>)> print>(f>'Height(Depth) of tree is: {height(root)}'>)> # This code is contributed by shinjanpatra>

>

>

C#

// C# Program to find the Maximum Depth or Height of Binary Tree> using> System;> using> System.Collections.Generic;> // A Tree node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left =>null>;> >right =>null>;> >}> }> public> class> BinaryTree {> >Node root;> >// Function to find the height(depth) of the tree> >int> height()> >{> >// Initialising a variable to count the> >// height of tree> >int> depth = 0;> >Queue q =>new> Queue();> >// Pushing first level element along with NULL> >q.Enqueue(root);> >q.Enqueue(>null>);> >while> (q.Count != 0) {> >Node temp = q.Dequeue();> >// When NULL encountered, increment the value> >if> (temp ==>null>)> >depth++;> >// If NULL not encountered, keep moving> >if> (temp !=>null>) {> >if> (temp.left !=>null>) {> >q.Enqueue(temp.left);> >}> >if> (temp.right !=>null>) {> >q.Enqueue(temp.right);> >}> >}> >// If queue still have elements left,> >// push NULL again to the queue> >else> if> (q.Count != 0) {> >q.Enqueue(>null>);> >}> >}> >return> depth;> >}> >// Driver program> >public> static> void> Main()> >{> >// Let us create Binary Tree shown in above example> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(1);> >tree.root.left =>new> Node(2);> >tree.root.right =>new> Node(3);> >tree.root.left.left =>new> Node(4);> >tree.root.left.right =>new> Node(5);> >Console.WriteLine(>'Height(Depth) of tree is: '> >+ tree.height());> >}> }> // This code is contributed by Yash Agarwal(yashagarwal2852002)>

>

>

JavaScript

> // JavaScript code to implement the approach> // A Tree node> class Node{> >constructor(){> >this>.key = 0> >this>.left =>null> >this>.right =>null> >}> }> // Utility function to create a new node> function> newNode(key){> >let temp =>new> Node()> >temp.key = key> >temp.left =>null> >temp.right =>null> >return> temp> }> // Function to find the height(depth) of the tree> function> height(root){> >// Initialising a variable to count the> >// height of tree> >let depth = 0> >let q = []> > >// pushing first level element along with null> >q.push(root)> >q.push(>null>)> >while>(q.length>0){> >let temp = q.shift()> > >// When null encountered, increment the value> >if>(temp ==>null>)> >depth += 1> > >// If null not encountered, keep moving> >if>(temp !=>null>){> >if>(temp.left)> >q.push(temp.left)> > >if>(temp.right)> >q.push(temp.right)> >}> > >// If queue still have elements left,> >// push null again to the queue.> >else> if>(q.length>0)> >q.push(>null>)> >}> >return> depth> }> // Driver program> // Let us create Binary Tree shown in above example> let root = newNode(1)> root.left = newNode(2)> root.right = newNode(3)> root.left.left = newNode(4)> root.left.right = newNode(5)> document.write(`Height(Depth) of tree is: ${height(root)}`,>''>)> // This code is contributed by shinjanpatra> >

>

>

Producción

Height(Depth) of tree is: 3>

Complejidad del tiempo: EN)
Espacio Auxiliar: EN)

Otro método para encontrar la altura usando Recorrido de orden de nivel :

Este método también utiliza el concepto de recorrido de orden de nivel, pero no agregaremos valores nulos en la cola. Simplemente aumente el encimera cuando el nivel aumenta y empuja a los hijos del nodo actual a la cola, luego elimina todos los nodos de la cola del nivel actual.

C++

// C++ program for above approach> #include> using> namespace> std;> // A Tree node> struct> Node {> >int> key;> >struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->clave = clave;> >temp->izquierda = temp->derecha = NULL;> >return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(Node* root)> {> >// Initialising a variable to count the> >// height of tree> >queue q;> >q.push(root);> >int> height = 0;> >while> (!q.empty()) {> >int> size = q.size();> >for> (>int> i = 0; i Node* temp = q.front(); q.pop(); if (temp->izquierda != NULL) { q.push(temp->izquierda); } if (temperatura->derecha! = NULL) { q.push(temperatura->derecha); } } altura++; } altura de retorno; } // Programa controlador int main() { // Creemos el árbol binario que se muestra en el ejemplo anterior Nodo* root = newNode(1); raíz->izquierda = nuevoNodo(2); raíz->derecha = nuevoNodo(3); raíz->izquierda->izquierda = nuevoNodo(4); raíz->izquierda->derecha = nuevoNodo(5); corte<< 'Height(Depth) of tree is: ' << height(root); } // This code is contributed by Abhijeet Kumar(abhijeet19403)>

>

>

Java

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> >// A tree node structure> >static> class> Node {> >int> key;> >Node left;> >Node right;> >}> >// Utility function to create> >// a new node> >static> Node newNode(>int> key)> >{> >Node temp =>new> Node();> >temp.key = key;> >temp.left = temp.right =>null>;> >return> temp;> >}> >/*Function to find the height(depth) of the tree*/> >public> static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >Queue q =>new> LinkedList();> >q.add(root);> >int> height =>0>;> >while> (!q.isEmpty()) {> >int> size = q.size();> >for> (>int> i =>0>; i Node temp = q.poll(); if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } height++; } return height; } // Driver Code public static void main(String args[]) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); System.out.println('Height(Depth) of tree is: ' + height(root)); } }>

>

>

Python3

# Python3 program to find the height of a tree> > # A binary tree node> class> Node:> > ># Constructor to create a new node> >def> __init__(>self>, data):> >self>.key>=> data> >self>.left>=> None> >self>.right>=> None> > # Function to find height of tree> def> height(root):> ># Base Case> >if> root>is> None>:> >return> 0> > ># Create an empty queue for level order traversal> >q>=> []> > ># Enqueue Root and initialize height> >q.append(root)> >height>=> 0> > ># Loop while queue is not empty> >while> q:> > ># nodeCount (queue size) indicates number of nodes> ># at current level> >nodeCount>=> len>(q)> > ># Dequeue all nodes of current level and Enqueue all> ># nodes of next level> >while> nodeCount>>0>:> >node>=> q.pop(>0>)> >if> node.left>is> not> None>:> >q.append(node.left)> >if> node.right>is> not> None>:> >q.append(node.right)> >nodeCount>->=> 1> >height>+>=> 1> > >return> height> > # Driver Code> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> > print>(>'Height(Depth) of tree is'>, height(root))>

>

>

C#

using> System;> using> System.Collections.Generic;> class> GFG {> >// A Tree node> >class> Node {> >public> int> key;> >public> Node left, right;> >public> Node(>int> key)> >{> >this>.key=key;> >this>.left=>this>.right=>null>;> >}> >}> >// Utility function to create a new node> >/*Node newNode(int key)> >{> >Node* temp = new Node;> >temp.key = key;> >temp.left = temp.right = NULL;> >return (temp);> >}*/> >/*Function to find the height(depth) of the tree*/> >static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >Queue q=>new> Queue();> >q.Enqueue(root);> >int> height = 0;> >while> (q.Count>0) {> >int> size = q.Count;> >for> (>int> i = 0; i Node temp = q.Peek(); q.Dequeue(); if (temp.left != null) { q.Enqueue(temp.left); } if (temp.right != null) { q.Enqueue(temp.right); } } height++; } return height; } // Driver program public static void Main() { // Let us create Binary Tree shown in above example Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); Console.Write('Height(Depth) of tree is: ' + height(root)); } } // This code is contributed by poojaagarwal2.>

>

>

JavaScript

// JavaScript program for above approach> // a tree node> class Node{> >constructor(key){> >this>.key = key;> >this>.left =>this>.right =>null>;> >}> }> // utility function to create a new node> function> newNode(key){> >return> new> Node(key);> }> // function to find the height of the tree> function> height(root){> >// initialising a variable to count the> >// height of tree> >let q = [];> >q.push(root);> >let height = 0;> >while>(q.length>0){> >let size = q.length;> >for>(let i = 0; i let temp = q.shift(); if(temp.left != null){ q.push(temp.left); } if(temp.right != null){ q.push(temp.right); } } height++; } return height; } // driver code let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); document.write('Height(Depth) of tree is: ' + height(root)); // this code is contributed by Kirti Agarwal(kirtiagarwal23121999)>

>

>

Producción

Height(Depth) of tree is: 3>

Complejidad del tiempo: EN)
Espacio Auxiliar: EN)