Last Updated on November 30, 2023 by Ankit Kochar
The diameter of a binary tree is a fundamental metric used in understanding the structure and efficiency of tree-based algorithms. It represents the longest path between any two nodes in the tree, measured by the number of edges between them. Calculating the diameter of a binary tree involves traversing the tree and finding the maximum distance between two nodes. This critical measurement plays a significant role in optimizing algorithms, such as tree-based data structures, network routing, and more.
How to Find the Diameter of a Binary Tree?
Given a binary tree, find its diameter. The diameter of a binary tree refers to the longest distance between any two nodes in the binary tree and there is no compulsion on the path, it may or may not pass through the root node.
Let’s understand this with the help of some sample examples.
Example 1
Input
Output
4Explanation of the above example
In the above example, the longest path is of length 4 and the path is 7 – 4 – 8 – 1 – 3.
Example 2
Input
Output
6Explanation of the above example
In the above example, the longest path is of length 6 and is not passing through the root. And the path is 5 – 3 – 1 – 8 – 0 – 2 – 0.
Solution for Finding the Diameter of Binary Tree: Brute Force
In this approach, we will consider every node of the binary tree as the curving point. We can understand a curving point as the diameter path which has the maximum height. In the above-mentioned example, the curving points are 4 and 8 respectively.
The diameter is nothing but the maximum of the height of the left subtree+ height of the right subtree. So in this approach, we will travel to each node and calculate the height of its left and right subtree and find the maximum. After traversing the complete binary tree we will have our diameter with us.
Algorithm of Finding the Diameter of Binary Tree by Brute Force
We have explained the algorithm of the above-mentioned approach below.
- Travel the whole tree recursively.
- At each node calculate the height of the left and right subtree.
- Now calculate the diameter by adding the length of both the left and right subtrees.
- Now calculate the maximum diameter.
- You can do this by passing any variable by reference and with each recursive call updating the value of that variable.
Dry Run of the above Approach
Now, we will discuss the dry run for the brute force of finding the diameter of a binary tree.
- First, we will initialize the maximum diameter variable with the minimum value possible so INT_MIN.
- Now on node 5, the left height is 1, right height is 4 hence the value of diameter is 1+4=5. Currently, it is the max value so currently, so the diameter is 5.
- On node 9 the left height and right height are 0 as it is a leaf node so its diameter is 0 but it is not the maximum value we have so the diameter is currently 5.
- On node 4 the left height and right height are 3 hence the diameter is 6 so is the max value now.
- On node 7 left height is 2 right height is 0 current diameter is 2 but not max.
- For node 2 the left height is 1 and the right height is 1 so the diameter is 1 but not the max value.
- 12 is a leaf node so the diameter for leaf nodes like 12,0,3 in the above example will be 0.
- Similarly, we can do this for the remaining nodes, as we have explained in the image. But they will not change the value of the max diameter as they are smaller than the current max value.
Hence the maximum value of diameter will be 6.
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
struct node* newNode(int data);
int max(int a, int b) { return (a > b) ? a : b; }
int height(struct node* node);
int diameter(struct node* tree)
{ if (tree == NULL)
return 0;
int lheight = height(tree->left);
int rheight = height(tree->right);
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
return max(lheight + rheight + 1,
max(ldiameter, rdiameter));
}
int height(struct node* node)
{
if (node == NULL)
return 0;
return 1 + max(height(node->left), height(node->right));
}
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);
}
int main()
{
struct node* root = newNode(11);
root->left = newNode(21);
root->right = newNode(31);
root->left->left = newNode(14);
root->left->right = newNode(15);
cout << "Diameter of the given binary tree is "
<< diameter(root);
return 0;
}
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
int diameter(Node root)
{
if (root == null)
return 0;
int lheight = height(root.left);
int rheight = height(root.right);
int ldiameter = diameter(root.left);
int rdiameter = diameter(root.right);
return Math.max(lheight + rheight + 1,Math.max(ldiameter, rdiameter));
}
int diameter() { return diameter(root); }
static int height(Node node)
{
if (node == null)
return 0;
return (1
+ Math.max(height(node.left),
height(node.right)));
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(11);
tree.root.left = new Node(21);
tree.root.right = new Node(31);
tree.root.left.left = new Node(14);
tree.root.left.right = new Node(15);
System.out.println(
"The diameter of given binary tree is : "
+ tree.diameter());
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
def diameter(root):
if root is None:
return 0
lheight = height(root.left)
rheight = height(root.right)
ldiameter = diameter(root.left)
rdiameter = diameter(root.right)
return max(lheight + rheight + 1, max(ldiameter, rdiameter))
if __name__ == "__main__":
root = Node(11)
root.left = Node(21)
root.right = Node(31)
root.left.left = Node(14)
root.left.right = Node(15)
print(diameter(root))
Output
Diameter of the given binary tree is 4Explanation of the above example
We have to find the diameter of the binary tree using the above approach by finding the diameter at each node and then printing the max among all of them.
Time Complexity
The time complexity of the above approach will be O(N*N) where N is the number of nodes in the binary tree.
Space Complexity
O(1) extra space and O(H) will be recursive stack space where H is the height of the binary tree.
Solution for Finding the Diameter of Binary Tree: Optimized Approach
In this blog section, we will discuss the optimized approach for finding the diameter of a binary tree. The approach gives us the correct answer but can you think of anything this is repeating in the above approach? The answer is the height of subtrees.
To solve this we can use the post-order traversal as in post-order traversal we will travel to left and right subtrees first before going to the node so that in one recursion we can find the height and diameter of the node together.
Algorithm of Finding the Diameter of Binary Tree by Optimized Approach
We will now discuss the algorithm for the above-mentioned approach.
- Start traversing the tree but now in the post order.
- Do all the steps like calculating the height of the left and right subtrees and the diameter of the current node but in post order.
- Compare the diameter of the current node with the stored diameter if the current diameter is maximum then update the value of the stored diameter, otherwise move on.
- Return the height of the current node to the last or previous recursive call.
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
struct node* newNode(int data);
int diameterOpt(struct node* root, int* height)
{
int lh = 0, rh = 0;
int ldiameter = 0, rdiameter = 0;
if (root == NULL) {
*height = 0;
return 0;
}
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);
*height = max(lh, rh) + 1;
return max(lh + rh + 1, max(ldiameter, rdiameter));
}
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);
}
int main()
{
struct node* root = newNode(11);
root->left = newNode(21);
root->right = newNode(31);
root->left->left = newNode(14);
root->left->right = newNode(15);
int height = 0;
// Function Call
cout << "Diameter of the given binary tree is "
<< diameterOpt(root, &height);
return 0;
} // Recursive Java program to find the diameter of a
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
class Height {
int h;
}
class BinaryTree {
Node root;
int diameterOpt(Node root, Height height)
{
Height lh = new Height(), rh = new Height();
if (root == null) {
height.h = 0;
return 0;
}
int ldiameter = diameterOpt(root.left, lh);
int rdiameter = diameterOpt(root.right, rh);
height.h = Math.max(lh.h, rh.h) + 1;
return Math.max(lh.h + rh.h + 1,
Math.max(ldiameter, rdiameter));
}
int diameter()
{
Height height = new Height();
return diameterOpt(root, height);
}
static int height(Node node)
{
if (node == null)
return 0;
return (1
+ Math.max(height(node.left),
height(node.right)));
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(11);
tree.root.left = new Node(21);
tree.root.right = new Node(31);
tree.root.left.left = new Node(14);
tree.root.left.right = new Node(15);
System.out.println(
"The diameter of given binary tree is : "
+ tree.diameter());
}
}
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None
class Height:
def __init(self):
self.h = 0
def diameterOpt(root, height):
lh = Height()
rh = Height()
if root is None:
height.h = 0
return 0
ldiameter = diameterOpt(root.left, lh)
rdiameter = diameterOpt(root.right, rh)
height.h = max(lh.h, rh.h) + 1
return max(lh.h + rh.h + 1, max(ldiameter, rdiameter))
def diameter(root):
height = Height()
return diameterOpt(root, height)
if __name__ == "__main__":
root = Node(11)
root.left = Node(21)
root.right = Node(31)
root.left.left = Node(14)
root.left.right = Node(15)
print("The diameter of the binary tree is:", end=" ")
print(diameter(root))
Output
The diameter of the binary tree is: 4Explanation of the above approach
We have used the above-mentioned approach in the above codes as with the help of post-order traversal we can find the diameter and height in a single recursion.
Time Complexity
O(N) as we are traversing the whole tree.
Space Complexity
The space complexity will be O(N) as we are recursing the whole tree.
Conclusion
Understanding the diameter of a binary tree is crucial in various computer science applications. It helps in optimizing algorithms that involve tree structures, enabling efficient problem-solving across different domains. By determining the longest path between nodes within a binary tree, developers can enhance the performance and scalability of their applications. The diameter metric provides valuable insights into the structure of the tree, aiding in algorithmic optimizations and improved system design.
Frequently Asked Questions on Diameter of a Binary Tree
Here are some of the frequently asked questions about the diameter of a binary tree.
1. Can the diameter of a binary tree be negative?
No, the diameter of a binary tree cannot be negative.
2. How is the diameter of a binary tree calculated?
To calculate the diameter of a binary tree, you perform a depth-first traversal to find the longest path between two nodes. This is typically done by finding the height of the left and right subtrees for each node and then computing the maximum diameter among all nodes.
3. What is the significance of the diameter of a binary tree?
The diameter provides essential insights into the structure of the tree. It helps in optimizing algorithms that rely on tree-based data structures, such as optimizing network routing, designing efficient data storage systems, and solving various graph-related problems.
4. Can the diameter of a binary tree be zero?
Yes, the diameter of a binary tree can be zero. This occurs when the tree consists of either a single node or no node at all. In such cases, the maximum distance between any two nodes is zero.
5. How does the diameter impact the efficiency of algorithms?
Understanding the diameter allows for the optimization of algorithms by providing information about the longest path within the tree. Algorithms can be designed or modified to take advantage of this information, improving their efficiency and reducing computational complexity.