Open In App

Diameter of a Binary Tree

Last Updated : 17 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

The diameter/width of a tree is defined as the number of nodes on the longest path between two end nodes. 

The diagram below shows two trees each with a diameter of nine, the leaves that form the ends of the longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes). 

Approach: The diameter of a tree T is the largest of the following quantities:

  • The diameter of T’s left subtree.
  • The diameter of T’s right subtree.
  • The longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

Below is the implementation of the above approach

C++
// Recursive optimized C program to find the diameter of a
// Binary Tree
#include <bits/stdc++.h>
using namespace std;

// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
    int data;
    struct node *left, *right;
};

// function to create a new node of tree and returns pointer
struct node* newNode(int data);

// returns max of two integers
int max(int a, int b) { return (a > b) ? a : b; }

// function to Compute height of a tree.
int height(struct node* node);

// Function to get diameter of a binary tree
int diameter(struct node* tree)
{
    // base case where tree is empty
    if (tree == NULL)
        return 0;

    // get the height of left and right sub-trees
    int lheight = height(tree->left);
    int rheight = height(tree->right);

    // get the diameter of left and right sub-trees
    int ldiameter = diameter(tree->left);
    int rdiameter = diameter(tree->right);

    // Return max of following three
    // 1) Diameter of left subtree
    // 2) Diameter of right subtree
    // 3) Height of left subtree + height of right subtree +
    // 1
    return max(lheight + rheight + 1,
               max(ldiameter, rdiameter));
}

// UTILITY FUNCTIONS TO TEST diameter() FUNCTION

// The function Compute the "height" of a tree. Height is
// the number f nodes along the longest path from the root
// node down to the farthest leaf node.
int height(struct node* node)
{
    // base case tree is empty
    if (node == NULL)
        return 0;

    // If tree is not empty then height = 1 + max of left
    // height and right heights
    return 1 + max(height(node->left), height(node->right));
}

// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

// Driver Code
int main()
{

    /* Constructed binary tree is
            1
            / \
        2     3
        / \
    4     5
    */
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Function Call
    cout << "Diameter of the given binary tree is "
         << diameter(root);

    return 0;
}

// This code is contributed by shivanisinghss2110
C
// Recursive optimized C program to find the diameter of a
// Binary Tree
#include <stdio.h>
#include <stdlib.h>

// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
    int data;
    struct node *left, *right;
};

// function to create a new node of tree and returns pointer
struct node* newNode(int data);

// returns max of two integers
int max(int a, int b) { return (a > b) ? a : b; }

// function to Compute height of a tree.
int height(struct node* node);

// Function to get diameter of a binary tree
int diameter(struct node* tree)
{
    // base case where tree is empty
    if (tree == NULL)
        return 0;

    // get the height of left and right sub-trees
    int lheight = height(tree->left);
    int rheight = height(tree->right);

    // get the diameter of left and right sub-trees
    int ldiameter = diameter(tree->left);
    int rdiameter = diameter(tree->right);

    // Return max of following three
    // 1) Diameter of left subtree
    // 2) Diameter of right subtree
    // 3) Height of left subtree + height of right subtree +
    // 1

    return max(lheight + rheight + 1,
               max(ldiameter, rdiameter));
}

// UTILITY FUNCTIONS TO TEST diameter() FUNCTION

//  The function Compute the "height" of a tree. Height is
//  the number f nodes along the longest path from the root
//   node down to the farthest leaf node.
int height(struct node* node)
{
    // base case tree is empty
    if (node == NULL)
        return 0;

    // If tree is not empty then height = 1 + max of left
    // height and right heights
    return 1 + max(height(node->left), height(node->right));
}

// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

// Driver Code
int main()
{

    /* Constructed binary tree is
              1
            /   \
          2      3
        /  \
      4     5
    */
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Function Call
    printf("Diameter of the given binary tree is %d\n",
           diameter(root));

    return 0;
}
Java
// Recursive optimized Java program to find the diameter of
// a Binary Tree

// Class containing left and right child of current
// node and key value
class Node {
    int data;
    Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

// Class to print the Diameter
class BinaryTree {
    Node root;

    // Method to calculate the diameter and return it to
    // main
    int diameter(Node root)
    {
        // base case if tree is empty
        if (root == null)
            return 0;

        // get the height of left and right sub-trees
        int lheight = height(root.left);
        int rheight = height(root.right);

        // get the diameter of left and right sub-trees
        int ldiameter = diameter(root.left);
        int rdiameter = diameter(root.right);

        /* Return max of following three
          1) Diameter of left subtree
          2) Diameter of right subtree
          3) Height of left subtree + height of right
          subtree + 1
         */
        return Math.max(lheight + rheight + 1,
                        Math.max(ldiameter, rdiameter));
    }

    // A wrapper over diameter(Node root)
    int diameter() { return diameter(root); }

    // The function Compute the "height" of a tree. Height
    // is the number of nodes along the longest path from
    // the root node down to the farthest leaf node.
    static int height(Node node)
    {
        // base case tree is empty
        if (node == null)
            return 0;

        // If tree is not empty then height = 1 + max of
        //  left height and right heights
        return (1
                + Math.max(height(node.left),
                           height(node.right)));
    }

    // Driver Code
    public static void main(String args[])
    {
        // creating a binary tree and entering the nodes
        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);

        // Function Call
        System.out.println(
            "The diameter of given binary tree is : "
            + tree.diameter());
    }
}
Python3
# Python3 program to find the diameter of binary tree

# A binary tree node


class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# The function Compute the "height" of a tree. Height is the
# number of nodes along the longest path from the root node
# down to the farthest leaf node.

def height(node):

    # Base Case : Tree is empty
    if node is None:
        return 0

    # If tree is not empty then height = 1 + max of left
    # height and right heights
    return 1 + max(height(node.left), height(node.right))

# Function to get the diameter of a binary tree


def diameter(root):

    # Base Case when tree is empty
    if root is None:
        return 0

    # Get the height of left and right sub-trees
    lheight = height(root.left)
    rheight = height(root.right)

    # Get the diameter of left and right sub-trees
    ldiameter = diameter(root.left)
    rdiameter = diameter(root.right)

    # Return max of the following tree:
    # 1) Diameter of left subtree
    # 2) Diameter of right subtree
    # 3) Height of left subtree + height of right subtree +1
    return max(lheight + rheight + 1, max(ldiameter, rdiameter))


# Driver Code
if __name__ == "__main__":
    """
    Constructed binary tree is 
                1
              /   \
            2      3
          /  \
        4     5
    """

    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    # Function Call
    print(diameter(root))

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// Recursive optimized C# program to find the diameter of
// a Binary Tree

// Class containing left and right child of current
// node and key value
using System;

namespace Tree {
class Tree<T> {
    public Tree(T value) { this.value = value; }
    public T value
    {
        get;
        set;
    }
    public Tree<T> left
    {
        get;
        set;
    }
    public Tree<T> right
    {
        get;
        set;
    }
}

public class TreeDiameter {
    Tree<int> root;

    // The function Compute the "height" of a tree. Height
    // is the number of nodes along the longest path from
    // the root node down to the farthest leaf node.
    int Height(Tree<int> node)
    {
        if (node == null)
            return 0;
        return 1
            + Math.Max(Height(node.left),
                       Height(node.right));
    }
    int Diameter(Tree<int> root)
    {
        if (root == null)
            return 0;

        // get the height of left and right sub-trees
        int lHeight = Height(root.left);
        int rHeight = Height(root.right);

        // get the diameter of left and right sub-trees
        int lDiameter = Diameter(root.left);
        int rDiameter = Diameter(root.right);

        //  Return max of following three
        // 1) Diameter of left subtree
        // 2) Diameter of right subtree
        // 3) Height of left subtree + height of right
        // subtree + 1
        return Math.Max(lHeight + rHeight + 1,
                        Math.Max(lDiameter, rDiameter));
    }

    // A wrapper over diameter(Node root)
    int Diameter() { return Diameter(root); }

    // Driver Code
    public static void Main(string[] args)
    {

        // creating a binary tree and entering the nodes
        TreeDiameter tree = new TreeDiameter();
        tree.root = new Tree<int>(1);
        tree.root.left = new Tree<int>(2);
        tree.root.right = new Tree<int>(3);
        tree.root.left.left = new Tree<int>(4);
        tree.root.left.right = new Tree<int>(5);

        Console.WriteLine(
            "The diameter of given binary tree is : "
            + tree.Diameter());
    }
}
}

// This code is contributed by krishaccot
Javascript
<script>
// JavaScript program to find the diameter of binary tree
 
// A binary tree node
class Node{
   
  // Constructor to create a new node
  constructor(data){
    this.data = data
    this.left = null
    this.right = null 
  }

} 
 
// The function Compute the "height" of a tree. Height is the
// number of nodes along the longest path from the root node
// down to the farthest leaf node.
function height(node)
{

    // Base Case : Tree is empty
    if(node == null)
        return 0
 
    // If tree is not empty then height = 1 + max of left
    // height and right heights
    return 1 + Math.max(height(node.left), height(node.right))
}
 
// Function to get the diameter of a binary tree
function diameter(root){
 
    // Base Case when tree is empty
    if(root == null)
        return 0
 
    // Get the height of left and right sub-trees
    let lheight = height(root.left)
    let rheight = height(root.right)
 
    // Get the diameter of left and right sub-trees
    let ldiameter = diameter(root.left)
    let rdiameter = diameter(root.right)
 
    // Return max of the following tree:
    // 1) Diameter of left subtree
    // 2) Diameter of right subtree
    // 3) Height of left subtree + height of right subtree +1
    return Math.max(lheight + rheight + 1, Math.max(ldiameter, rdiameter))

}
 
 
// Driver Code

// Constructed binary tree is
//             1
//           /   \
//         2      3
//       /  \
//     4     5
 
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)
 
// Function Call
document.write("Diameter of the given binary tree is "+diameter(root))
 
// This code is contributed by shinjanpatra
</script>

Output
Diameter of the given binary tree is 4

Time Complexity: O(N2)
Auxiliary Space: O(N) for call stack
 
Efficient Approach: To solve the problem follow the below idea:

 The above implementation can be optimized by calculating the height in the same recursion rather than calling a height() separately. Thanks to Amar for suggesting this optimized version.

Below is the implementation of the above approach:

C++
// Recursive optimized C++ program to find the diameter of a
// Binary Tree
#include <bits/stdc++.h>
using namespace std;

// A binary tree node has data, pointer to left child
// and a pointer to right child
struct node {
    int data;
    struct node *left, *right;
};

// function to create a new node of tree and returns pointer
struct node* newNode(int data);

int diameterOpt(struct node* root, int* height)
{
    // lh --> Height of left subtree
    // rh --> Height of right subtree
    int lh = 0, rh = 0;

    // ldiameter  --> diameter of left subtree
    // rdiameter  --> Diameter of right subtree
    int ldiameter = 0, rdiameter = 0;

    if (root == NULL) {
        *height = 0;
        return 0; // diameter is also 0
    }

    // Get the heights of left and right subtrees in lh and
    // rh And store the returned values in ldiameter and
    // ldiameter
    ldiameter = diameterOpt(root->left, &lh);
    rdiameter = diameterOpt(root->right, &rh);

    // Height of current node is max of heights of left and
    // right subtrees plus 1
    *height = max(lh, rh) + 1;

    return max(lh + rh + 1, max(ldiameter, rdiameter));
}

// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

// Driver Code
int main()
{

    /* Constructed binary tree is
            1
            / \
        2     3
        / \
    4     5
    */
    struct node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    int height = 0;

    // Function Call
    cout << "Diameter of the given binary tree is "
         << diameterOpt(root, &height);

    return 0;
}

// This code is contributed by probinsah.
Java
// Recursive Java program to find the diameter of a
// Binary Tree

// Class containing left and right child of current
// node and key value
class Node {
    int data;
    Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

// A utility class to pass height object
class Height {
    int h;
}

// Class to print the Diameter
class BinaryTree {
    Node root;

    // define height =0 globally and  call
    // diameterOpt(root,height) from main
    int diameterOpt(Node root, Height height)
    {
        // lh --> Height of left subtree
        // rh --> Height of right subtree
        Height lh = new Height(), rh = new Height();

        if (root == null) {
            height.h = 0;
            return 0; // diameter is also 0
        }
        /*
                ldiameter  --> diameter of left subtree
                rdiameter  --> Diameter of right subtree
                Get the heights of left and right subtrees
           in lh and rh. And store the returned values in
           ldiameter and ldiameter*/
        int ldiameter = diameterOpt(root.left, lh);
        int rdiameter = diameterOpt(root.right, rh);

        // Height of current node is max of heights of left
        // and right subtrees plus 1
        height.h = Math.max(lh.h, rh.h) + 1;

        return Math.max(lh.h + rh.h + 1,
                        Math.max(ldiameter, rdiameter));
    }

    // A wrapper over diameter(Node root)
    int diameter()
    {
        Height height = new Height();
        return diameterOpt(root, height);
    }

    // The function Compute the "height" of a tree. Height
    // is
    //  the number f nodes along the longest path from the
    //  root node down to the farthest leaf node.
    static int height(Node node)
    {
        // base case tree is empty
        if (node == null)
            return 0;

        // If tree is not empty then height = 1 + max of
        // left height and right heights
        return (1
                + Math.max(height(node.left),
                           height(node.right)));
    }

    // Driver Code
    public static void main(String args[])
    {
        // creating a binary tree and entering the nodes
        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);

        // Function Call
        System.out.println(
            "The diameter of given binary tree is : "
            + tree.diameter());
    }
}
Python3
# Python3 program to find the diameter of a binary tree
# A binary tree Node


class Node:

    # Constructor to create a new Node
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

# utility class to pass height object


class Height:
    def __init(self):
        self.h = 0

# Optimised recursive function to find diameter
# of binary tree


def diameterOpt(root, height):

    # to store height of left and right subtree
    lh = Height()
    rh = Height()

    # base condition- when binary tree is empty
    if root is None:
        height.h = 0
        return 0

    # ldiameter --> diameter of left subtree
    # rdiameter  --> diameter of right subtree

    # height of left subtree and right subtree is obtained from lh and rh
    # and returned value of function is stored in ldiameter and rdiameter

    ldiameter = diameterOpt(root.left, lh)
    rdiameter = diameterOpt(root.right, rh)

    # height of tree will be max of left subtree
    # height and right subtree height plus1

    height.h = max(lh.h, rh.h) + 1

    # return maximum of the following
    # 1)left diameter
    # 2)right diameter
    # 3)left height + right height + 1
    return max(lh.h + rh.h + 1, max(ldiameter, rdiameter))

# function to calculate diameter of binary tree


def diameter(root):
    height = Height()
    return diameterOpt(root, height)


# Driver Code
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    """
  Constructed binary tree is 
              1
          /   \
          2      3
        /  \
      4     5
  """

    print("The diameter of the binary tree is:", end=" ")
    # Function Call
    print(diameter(root))

# This code is contributed by Shweta Singh(shweta44)
C#
// Recursive C# program to find the diameter of a
// Binary Tree
using System;
using System.Collections.Generic;

// Class containing left and right child of current
// node and key value
class Node {
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

// A utility class to pass height object
class Height {
    public int h;
}

// Class to print the Diameter
class BinaryTree {
    public Node root;

    // define height =0 globally and  call
    // diameterOpt(root,height) from main
    public int diameterOpt(Node root, Height height)
    {
        // lh --> Height of left subtree
        // rh --> Height of right subtree
        Height lh = new Height(), rh = new Height();

        if (root == null) {
            height.h = 0;
            return 0; // diameter is also 0
        }

        // ldiameter  --> diameter of left subtree
        // rdiameter  --> Diameter of right subtree
        // Get the heights of left and right subtrees in lh
        /*and rh And store the returned values in ldiameter
                and ldiameter */
        int ldiameter = diameterOpt(root.left, lh);
        int rdiameter = diameterOpt(root.right, rh);

        // Height of current node is max of heights of left
        // and right subtrees plus 1
        height.h = Math.Max(lh.h, rh.h) + 1;

        return Math.Max(lh.h + rh.h + 1,
                        Math.Max(ldiameter, rdiameter));
    }

    // A wrapper over diameter(Node root)
    public int diameter()
    {
        Height height = new Height();
        return diameterOpt(root, height);
    }

    // The function Compute the "height" of a tree. Height
    // is
    //  the number f nodes along the longest path from the
    //  root node down to the farthest leaf node.
    public int height(Node node)
    {
        // base case tree is empty
        if (node == null)
            return 0;

        // If tree is not empty then height = 1 + max of
        // left height and right heights
        return (1
                + Math.Max(height(node.left),
                           height(node.right)));
    }

    // Driver Code
    static void Main()
    {

        // creating a binary tree and entering the nodes
        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);

        // Function Call
        Console.Write(
            "The diameter of given binary tree is : "
            + tree.diameter());
    }
}

// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program to find the diameter of a binary tree
// A binary tree Node
class Node{

    // Constructor to create a new Node
    constructor(data){
        this.data = data
        this.left = this.right = null
    }
}

// utility class to pass height object
class Height
{
    constructor()
    {
        this.h = 0
    }
}

// Optimised recursive function to find diameter
// of binary tree
function diameterOpt(root, height){

    // to store height of left and right subtree
    let lh = new Height()
    let rh = new Height()

    // base condition- when binary tree is empty
    if(root == null)
    {
        height.h = 0
        return 0
    }

    
    // ldiameter --> diameter of left subtree
    // rdiameter  --> diameter of right subtree
    
    // height of left subtree and right subtree is obtained from lh and rh
    // and returned value of function is stored in ldiameter and rdiameter
    let ldiameter = diameterOpt(root.left, lh)
    let rdiameter = diameterOpt(root.right, rh)

    // height of tree will be max of left subtree
    // height and right subtree height plus1
    height.h = Math.max(lh.h, rh.h) + 1

    // return maximum of the following
    // 1)left diameter
    // 2)right diameter
    // 3)left height + right height + 1
    return Math.max(lh.h + rh.h + 1, Math.max(ldiameter, rdiameter))
}

// function to calculate diameter of binary tree
function diameter(root){
    let height = new Height()
    return diameterOpt(root, height)
}


// Driver Code 
let 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)


// Constructed binary tree is 
//             1
//           /   \
//         2      3
//       /  \
//     4     5


// Function Call
document.write(diameter(root))

// This code is contributed by Shinjanpatra

</script>

Output
Diameter of the given binary tree is 4

Time Complexity: O(N) 
Auxiliary Space: O(N) due to recursive calls.

Diameter of a Binary Tree using Morris Traversal Algorithm:

The main idea behind Morris Traversal is to modify the binary tree structure by creating a link from the rightmost node of the left subtree to its parent (as shown in the image below), which allows us to traverse the tree without using extra space for a stack or recursion.

morrisdrawio-(1)

Follow the steps below to implement the above idea:

  • Traverse the binary tree using a current_node initialised as the root of the binary tree.
  • While the current_node is not NULL, do the following
    • If the left child of the current node is NULL, move to the right child.
    • If the left child of the current node is not NULL, find the rightmost node in the left subtree of the current node.
    • If the right child of the rightmost node is NULL, set its right child to the current node, and move to the left child of the current node.
    • If the right child of the rightmost node is not NULL, set its right child back to NULL, visit the current node, and move to its right child.
    • For each visited node, calculate its left and right subtree heights using the maximum function and update the diameter as the maximum of the sum of their heights and the current diameter.
  • Return the diameter.

Below is the implementation of the above approach:

C++
// C++ code to implement the above approach that uses the
// morris traversal algorithm
#include <algorithm>
#include <iostream>

using namespace std;

// A tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

// Morris traversal to find the diameter of the binary tree
int findDiameter(Node* root)
{
    if(root == NULL)
        return 0;
    if(root->left==NULL && root->right==NULL)
        return 1;
    int ans = 0;
    Node* curr = root;

    while (curr != NULL) {
        if (curr->left == NULL) {
            curr = curr->right;
        }
        else {
            Node* pre = curr->left;
            while (pre->right != NULL && pre->right != curr)
                pre = pre->right;
            if (pre->right == NULL) {
                pre->right = curr;
                curr = curr->left;
            }
            else {
                pre->right = NULL;
                int leftHeight = 0, rightHeight = 0;
                Node* temp = curr->left;
                while (temp != NULL) {
                    leftHeight++;
                    temp = temp->right;
                }
                temp = curr->right;
                while (temp != NULL) {
                    rightHeight++;
                    temp = temp->left;
                }
                ans = max(ans,
                          leftHeight + rightHeight + 1);
                curr = curr->right;
            }
        }
    }
    return ans;
}

// Driver code
int main()
{
    // Create the given binary tree
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Find the diameter of the binary tree using Morris
    // traversal
    int diameter = findDiameter(root);

    // Print the diameter of the binary tree
    cout << "The diameter of given binary tree is "
         << diameter << endl;

    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
// This code is modified by Susobhan Akhuli
Java
//GFG
// Java code for this approach
class Node {
    int data;
    Node left, right;
  
    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class Main
{
  
    // Create a new node
    public static Node newNode(int data) {
        Node node = new Node(data);
        return node;
    }

    // Morris traversal to find the diameter of the binary tree
    public static int findDiameter(Node root) {
        if(root==null)
            return 0;
        if(root.left==null && root.right==null)
            return 1;
        int ans = 0;
        Node curr = root;

        while (curr != null) {
            if (curr.left == null) {
                curr = curr.right;
            } else {
                Node pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = curr;
                    curr = curr.left;
                } else {
                    pre.right = null;
                    int leftHeight = 0, rightHeight = 0;
                    Node temp = curr.left;
                    while (temp != null) {
                        leftHeight++;
                        temp = temp.right;
                    }
                    temp = curr.right;
                    while (temp != null) {
                        rightHeight++;
                        temp = temp.left;
                    }
                    ans = Math.max(ans, leftHeight + rightHeight + 1);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }

    // Driver code to test above function
    public static void main(String[] args)
    {
      
        // Create the given binary tree
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
        root.left.left = newNode(4);
        root.left.right = newNode(5);

        // Find the diameter of the binary tree using Morris traversal
        int diameter = findDiameter(root);

        // Print the diameter of the binary tree
        System.out.println("The diameter of given binary tree is " + diameter);
    }
}

// This code is written by Sundaram
// This code is modified by Susobhan Akhuli
Python3
# Python3 code to implement the above approach that uses the
# morris traversal algorithm

# A tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Create a new node
def newNode(data):
    node = Node(data)
    return node

# Morris traversal to find the diameter of the binary tree
def findDiameter(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    
    ans = 0
    curr = root

    while curr is not None:
        if curr.left is None:
            curr = curr.right
        else:
            pre = curr.left
            while pre.right is not None and pre.right != curr:
                pre = pre.right
            if pre.right is None:
                pre.right = curr
                curr = curr.left
            else:
                pre.right = None
                leftHeight = 0
                rightHeight = 0
                temp = curr.left
                while temp is not None:
                    leftHeight += 1
                    temp = temp.right
                temp = curr.right
                while temp is not None:
                    rightHeight += 1
                    temp = temp.left
                ans = max(ans, leftHeight + rightHeight + 1)
                curr = curr.right
    return ans


# Driver code
if __name__ == '__main__':
    # Create the given binary tree
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)

    # Find the diameter of the binary tree using Morris
    # traversal
    diameter = findDiameter(root)

    # Print the diameter of the binary tree
    print("The diameter of given binary tree is", diameter)

# This code is modified by Susobhan Akhuli
C#
using System;

public class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class Program {
    public static Node newNode(int data)
    {
        Node node = new Node(data);
        return node;
    }

    public static int findDiameter(Node root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
            
        int ans = 0;
        Node curr = root;

        while (curr != null) {
            if (curr.left == null) {
                curr = curr.right;
            }
            else {
                Node pre = curr.left;
                while (pre.right != null
                       && pre.right != curr) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    pre.right = curr;
                    curr = curr.left;
                }
                else {
                    pre.right = null;
                    int leftHeight = 0, rightHeight = 0;
                    Node temp = curr.left;
                    while (temp != null) {
                        leftHeight++;
                        temp = temp.right;
                    }

                    temp = curr.right;
                    while (temp != null) {
                        rightHeight++;
                        temp = temp.left;
                    }

                    ans = Math.Max(
                        ans, leftHeight + rightHeight + 1);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }

    public static void Main()
    {
        // Create the given binary tree
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
        root.left.left = newNode(4);
        root.left.right = newNode(5);

        // Find the diameter of the binary tree using Morris
        // traversal
        int diameter = findDiameter(root);

        // Print the diameter of the binary tree
        Console.WriteLine(
            "The diameter of given binary tree is "
            + diameter);
    }
}

// This code is modified by Susobhan Akhuli
Javascript
// A tree node
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// Create a new node
function newNode(data) {
    let node = new Node(data);
    return node;
}

// Morris traversal to find the diameter of the binary tree
function findDiameter(root) {
    if (root == null){
        return 0;
    }
    if(root.left == null && root.right == null){
        return 1;
    }
    
    let ans = 0;
    let curr = root;

    while (curr != null) {
        if (curr.left == null) {
            curr = curr.right;
        } else {
            let pre = curr.left;
            while (pre.right != null && pre.right != curr) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = curr;
                curr = curr.left;
            } else {
                pre.right = null;
                let leftHeight = 0, rightHeight = 0;
                let temp = curr.left;
                while (temp != null) {
                    leftHeight++;
                    temp = temp.right;
                }
                temp = curr.right;
                while (temp != null) {
                    rightHeight++;
                    temp = temp.left;
                }
                ans = Math.max(ans, leftHeight + rightHeight + 1);
                curr = curr.right;
            }
        }
    }
    return ans;
}

// Driver code to test above function
// Create the given binary tree
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);

// Find the diameter of the binary tree using Morris traversal
let diameter = findDiameter(root);

// Print the diameter of the binary tree
console.log("The diameter of given binary tree is " + diameter);

// This code is modified by Susobhan Akhuli

Output
The diameter of given binary tree is 4

Time Complexity: O(N), where N is the number of nodes in the binary tree
Auxiliary Space: O(h), The Morris Traversal approach does not use any additional data structures like stacks or queues, which leads to an auxiliary space complexity of O(1). However, the recursion stack used by the program contributes to a space complexity of O(h), where h is the height of the binary tree.

Related Article:
Diameter of a Binary Tree in O(n) [A new method]
Diameter of an N-ary tree


Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.



Previous Article
Next Article

Similar Reads

Diameter of a Binary Indexed Tree with N nodes
Given a Binary Indexed Tree with N nodes except root node 0 (Numbered from 1 to N), Find its diameter. Binary Indexed Tree is a tree where parent of a node number X = X - (X &amp; (X - 1)) i.e. last bit is unset in X. The diameter of a tree is the longest simple path between any two leaves. Examples: Input: N = 12 Output: 6 Explanation: Path from n
7 min read
Finding the lexicographically smallest diameter in a binary tree
Given a binary tree where node values are lowercase alphabets, the task is to find the lexicographically smallest diameter. Diameter is the longest path between any two leaf nodes, hence, there can be multiple diameters in a Binary Tree. The task is to print the lexicographically smallest diameter among all possible diameters.Examples: Input: a / \
13 min read
Diameter of a Binary Tree in O(n) [A new method]
The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of the longest path are colored (note that there may be more than one path in the tree of the same diameter).  Examples:  Input : 1 / \ 2 3 / \ 4 5Output : 4Input
6 min read
Diameter of n-ary tree using BFS
N-ary tree refers to the rooted tree in which each node having atmost k child nodes. The diameter of n-ary tree is the longest path between two leaf nodes. Various approaches have already been discussed to compute diameter of tree. Diameter of an N-ary tree Diameter of a Binary Tree in O(n) Diameter of a Binary Tree Diameter of a tree using DFS Thi
7 min read
Possible edges of a tree for given diameter, height and vertices
Find a tree with the given values and print the edges of the tree. Print "-1", if the tree is not possible. Given three integers n, d and h. n -&gt; Number of vertices. [1, n] d -&gt; Diameter of the tree (largest distance between two vertices). h -&gt; Height of the tree (longest distance between vertex 1 and another vertex) Examples : Input : n =
8 min read
DP on Trees | Set-3 ( Diameter of N-ary Tree )
Given an N-ary tree T of N nodes, the task is to calculate the longest path between any two nodes(also known as the diameter of the tree). Example 1: Example 2: Different approaches to solving these problems have already been discussed: https://www.geeksforgeeks.org/diameter-n-ary-tree/https://www.geeksforgeeks.org/diameter-n-ary-tree-using-bfs/ In
9 min read
Make a tree with n vertices , d diameter and at most vertex degree k
Given three integers N, D and K. The task is to check whether it is possible to make a tree with exactly N vertices, D diameter (the number of edges in the longest path between any two vertices), and degree of each vertex must be at most K. If it is possible then print all the possible edges otherwise print No. Examples: Input: N = 6, D = 3, K = 4
11 min read
Diameter of a tree using DFS
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with a diameter of five, the leaves that form the ends of the longest path are shaded (note that there is more than one path in each tree of length five, but no path longer than five n
8 min read
Diameter of an N-ary tree
The diameter of an N-ary tree is the longest path present between any two nodes of the tree. These two nodes must be two leaf nodes. The following examples have the longest path[diameter] shaded. Example 1: Example 2:  Prerequisite: Diameter of a binary tree. The path can either start from one of the nodes and go up to one of the LCAs of these node
15+ min read
CSES Solutions - Tree Diameter
You are given a tree consisting of n nodes. The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree. Examples: Input: n = 5, edges = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } };Output: 3 Input: n = 4, edges = { { 1, 2 }, { 1, 3 }, { 3, 4 }};Output: 3 Approach: We can uses a Depth-First Sea
6 min read
three90RightbarBannerImg