When you are working on a large amount of data, every data element is attached to other data elements in one way or another. Using sequential data structure always fails to reflect this relationship between the data and that’s where the non-sequential data structure such as trees, graphs, files, etc comes into the picture. In this article, we will learn what is the diameter of a binary tree and how to calculate it using two different approaches along with python code. But before moving forward, let us understand the binary tree in detail below.
What is a Binary Tree?
Trees are widely used as an abstract data structure that simulates the hierarchical structure to store data. The tree consists of nodes to represent the data as shown in the below image. The topmost node is known as the root node and the bottommost node is known as a leaf node.
A general tree data structure has no limitation for the number of child nodes and leaf nodes. But when it comes to a binary tree, the given condition changes. A binary tree is the type of tree data structure that possesses a maximum of two children nodes for each parent node. Each of these children's nodes is generally referred to as the left child and right child respectively. The below image represents the binary tree data structure.
A binary tree is further divided into two parts:
- Rooted Binary Tree: It consists of the root nodes and every node has a maximum of two children nodes.
- Fully Binary Tree: It consists of the root node and every other node in the tree has either 0 or 2 children exactly.
As the binary tree is a widely used data structure, you are most likely to face competitive questions related to it while cracking the interview of your dream company. One such question is calculating the diameter of a binary tree. So, let’s dive deep into finding the solution to this problem after defining the diameter of the binary tree below.
What is the diameter of a binary tree?
The diameter of the binary tree is defined as the total number of nodes on the longest path between two end nodes. Remember that this node is not compulsory to pass through the root node of the tree. For example, the below image shows the diameter of the tree from the left side to the right side passing through the root node.
In the above image, the diameter of the binary tree is calculated via root node i.e., D-B-A-C-E-G. Whereas the below image shows the diameter of the binary tree from the left side to the right side without passing through the root node i.e., G-E-C-F.
How to Calculate Diameter of Binary Tree?
Below are the two approaches by which you can find the diameter of the binary tree:
1) Calculating the Diameter of Binary Tree Using Recursive Approach
If you observe at the above images, the diameter of the binary tree is the maximum sum of heights of the left subtree and right subtree. Also, the diameter of every subtree may or may not include the sub-root in the calculation. If it does, then the final equation for the diameter of the binary tree will be:
Diameter = Left subtree height + Right subtree height + 1
Using the recursive approach, you can calculate the height of the left subtree and right subtree recursively from the left node. Later, calculate the diameter of the left-subtree and right-subtree as shown in the below visual. The maximum of both will be your final output.
As seen in the above illustration, there are multiple options as the diameter of a binary tree. However, at last, we should choose the option displaying the longest diameter of binary tree shown in the green color that is 73-74-75-50-100-150-125-130-131.
Algorithm for Recursive Approach
Repeat the above process recursively until NULL nodes are encountered.
Python Code for Recursive Approach
The time complexity of the above approach is O(n^2) where n is the number of nodes in the tree. It is because, the function recursively calls itself, and hence, every node is visited at least twice while calculating the diameter. However, the space complexity of the recursive approach is O(n) because of recursion.
2) Calculating the Diameter of Binary Tree Using Iterative Approach
You can also find the diameter of the binary tree using the iterative approach by the Depth First Search algorithm. As the diameter is always defined as the path between two leaf nodes of a binary tree, if you find the farthest node from the leaf node, you can easily calculate the diameter of the tree. This method is also called the Iterative method and provides me with the optimized solution for calculating the diameter of a binary tree.
Algorithm for Iterative Approach
Python Code for Iterative Approach
The time complexity using this approach is O(n) and therefore, it is considered to be an optimized solution for calculating the diameter of a binary tree. It is because using the iterative approach, we only visit the nodes of the tree once. At the same time, the space complexity of this approach is also O(n) where n is the number of nodes present in the tree.
Applications for Diameter of Binary Tree
1) Diameter of the binary tree is used to calculate the route during inter-processor communication within the network of any structure.
2) The DADO, a special purpose parallel computer make use of a binary tree interconnection network for faster execution of AI-oriented, rule-based software
A binary tree is an ideal way to store your data in a hierarchical manner and later access it efficiently whenever necessary. It is quite flexible in comparison to other data structures in any programming language. Finding the diameter of a binary tree is one of the fundamental problems that you can come across while understanding binary trees. Therefore, in this article, we have provided two basic approaches to calculate the diameter along with its algorithm and python code.