Diámetro de un Árbol Binario en O(n) [Un nuevo método]

El diámetro de un árbol es el número de Nodes en el camino más largo entre dos hojas del árbol. El siguiente diagrama muestra dos árboles cada uno con un diámetro de nueve, las hojas que forman los extremos del camino más largo están coloreadas (tenga en cuenta que puede haber más de un camino en el árbol del mismo diámetro).
 

Ejemplos: 

Input :     1
          /   \
        2      3
      /  \
    4     5

Output : 4

Input :     1
          /   \
        2      3
      /  \ .    \
    4     5 .    6

Output : 5

Hemos discutido una solución en la publicación a continuación. 
Diámetro de un árbol binario

En esta publicación se analiza un nuevo método O(n) simple. El diámetro de un árbol se puede calcular usando solo la función de altura, porque el diámetro de un árbol no es más que el valor máximo de (left_height + right_height + 1) para cada Node. Entonces necesitamos calcular este valor (left_height + right_height + 1) para cada Node y actualizar el resultado. Complejidad del tiempo – O(n)  

Implementación:

// Simple C++ program to find diameter
// of a binary tree.
#include <bits/stdc++.h>
using namespace std;
 
/* Tree node structure used in the program */
struct Node {
    int data;
    Node* left, *right;
};
 
/* Function to find height of a tree */
int height(Node* root, int& ans)
{
    if (root == NULL)
        return 0;
 
    int left_height = height(root->left, ans);
 
    int right_height = height(root->right, ans);
 
    // update the answer, because diameter of a
    // tree is nothing but maximum value of
    // (left_height + right_height + 1) for each node
    ans = max(ans, 1 + left_height + right_height);
 
    return 1 + max(left_height, right_height);
}
 
/* Computes the diameter of binary tree with given root. */
int diameter(Node* root)
{
    if (root == NULL)
        return 0;
    int ans = INT_MIN; // This will store the final answer
    height(root, ans);
    return ans;
}
 
struct Node* newNode(int data)
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
 
    return (node);
}
 
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    printf("Diameter is %d\n", diameter(root));
 
    return 0;
}

// Simple Java program to find diameter
// of a binary tree.
class GfG {
 
/* Tree node structure used in the program */
static class Node
{
    int data;
    Node left, right;
}
 
static class A
{
    int ans = Integer.MIN_VALUE;
}
 
/* Function to find height of a tree */
static int height(Node root, A a)
{
    if (root == null)
        return 0;
 
    int left_height = height(root.left, a);
 
    int right_height = height(root.right, a);
 
    // update the answer, because diameter of a
    // tree is nothing but maximum value of
    // (left_height + right_height + 1) for each node
    a.ans = Math.max(a.ans, 1 + left_height +
                    right_height);
 
    return 1 + Math.max(left_height, right_height);
}
 
/* Computes the diameter of binary
tree with given root. */
static int diameter(Node root)
{
    if (root == null)
        return 0;
 
    // This will store the final answer
    A a = new A();
    int height_of_tree = height(root, a);
    return a.ans;
}
 
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
 
    return (node);
}
 
// 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("Diameter is " + diameter(root));
}
}
 
// This code is contributed by Prerna Saini.

# Simple Python3 program to find diameter
# of a binary tree.
 
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
 
# Function to find height of a tree
def height(root, ans):
    if (root == None):
        return 0
 
    left_height = height(root.left, ans)
 
    right_height = height(root.right, ans)
 
    # update the answer, because diameter
    # of a tree is nothing but maximum
    # value of (left_height + right_height + 1)
    # for each node
    ans[0] = max(ans[0], 1 + left_height +
                             right_height)
 
    return 1 + max(left_height,
                   right_height)
 
# Computes the diameter of binary
# tree with given root.
def diameter(root):
    if (root == None):
        return 0
    ans = [-999999999999] # This will store
                          # the final answer
    height_of_tree = height(root, ans)
    return ans[0]
 
# Driver code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
 
    print("Diameter is", diameter(root))
 
# This code is contributed by PranchalK

// Simple C# program to find diameter
// of a binary tree.
using System;
 
class GfG
{
 
/* Tree node structure used in the program */
class Node
{
    public int data;
    public Node left, right;
}
 
class A
{
    public int ans = int.MinValue;
}
 
/* Function to find height of a tree */
static int height(Node root, A a)
{
    if (root == null)
        return 0;
 
    int left_height = height(root.left, a);
 
    int right_height = height(root.right, a);
 
    // update the answer, because diameter of a
    // tree is nothing but maximum value of
    // (left_height + right_height + 1) for each node
    a.ans = Math.Max(a.ans, 1 + left_height +
                    right_height);
 
    return 1 + Math.Max(left_height, right_height);
}
 
/* Computes the diameter of binary
tree with given root. */
static int diameter(Node root)
{
    if (root == null)
        return 0;
 
    // This will store the final answer
    A a = new A();
    int height_of_tree = height(root, a);
    return a.ans;
}
 
static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = null;
    node.right = null;
 
    return (node);
}
 
// Driver code
public static void Main()
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
 
    Console.WriteLine("Diameter is " + diameter(root));
}
}
 
/* This code is contributed by Rajput-Ji*/

<script>
 
    // Simple Javascript program to find
    // diameter of a binary tree.
     
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
     
    let ans = Number.MIN_VALUE;
     
    /* Function to find height of a tree */
    function height(root)
    {
        if (root == null)
            return 0;
 
        let left_height = height(root.left);
 
        let right_height = height(root.right);
 
        // update the answer, because diameter of a
        // tree is nothing but maximum value of
        // (left_height + right_height + 1) for each node
        ans = Math.max(ans, 1 + left_height +
                        right_height);
 
        return 1 + Math.max(left_height, right_height);
    }
 
    /* Computes the diameter of binary
    tree with given root. */
    function diameter(root)
    {
        if (root == null)
            return 0;
 
        // This will store the final answer
        let height_of_tree = height(root);
        return ans;
    }
 
    function newNode(data)
    {
        let node = new Node(data);
        return (node);
    }
     
    let root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
  
    document.write("Diameter is " + diameter(root));
     
</script>

Diameter is 4

Complejidad de tiempo: O(n),   donde n es el número de Nodes en el árbol binario.
Espacio auxiliar: O(h) para la pila de llamadas, donde h es la altura del árbol binario.

Este artículo es una contribución de Pooja Kamal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.