Last Updated on March 24, 2023 by Prepbytes
During an interview related to technical fields like Software engineer, product manager, etc. You will be asked questions based on data structures and algorithms and among all the data structures the binary tree is one of the most asked and important topics that have a very high chance that it will be asked in your interview. There are many standard questions that one can ask from the binary tree but if you know the properties of the binary tree and the traversing techniques then there are high chances that you can try to solve the questions.
We will here discuss one of the questions related to binary trees i.e, Find the diameter of a binary tree.
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
In summarizing the diameter of a binary tree can be referred to as the longest path between two nodes of a binary tree and the past may or may not pass through the root element of the binary tree. We have discussed two approaches to this question and they are brute force and an optimized approach. We have used the concept of finding the height of the binary tree and post-order traversal.
Frequently Asked Questions
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. Can the diameter of a binary tree be zero?
Yes, the diameter of a binary tree can be zero if the tree has only one node.
3. What is the relationship between the diameter of a binary tree and its height?
The diameter of a binary tree is not necessarily equal to its height. However, the diameter of a binary tree is always less than or equal to twice its height.
4. Can a binary tree have multiple diameters?
Yes, a binary tree can have multiple diameters if there are multiple pairs of nodes with the same maximum distance between them.