What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Diameter of Binary Tree (With Python Code)

  • Nov 19, 2021
  • 7 Minutes Read
Diameter of Binary Tree (With Python Code)

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.

Tree example

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.

Binary Tree Example

A binary tree is further divided into two parts:

  1. Rooted Binary Tree: It consists of the root nodes and every node has a maximum of two children nodes.
  2. 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.

Calculating the diameter of Binary tree via 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.

Calculating the diameter of Binary tree without root node

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. 

Calculating diamater of binary tree

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

1) Node passed in recursive function is null then return zero

2) Find the height of the left subtree

3) Find the height of the right subtree

4) Using recursive call, calculate the diameter of left-subtree until node becomes NULL

5) Using recursive call, calculate the diameter of right-subtree until node becomes NULL

6) If the root node is included then,

      Diameter = left-subtree + right-subtree + 1

7) If the root node is not included then,

      Diameter = max(diameter of left-subtree, diameter of right subtree)

8) The final output will return the max of step 6 and step 7

 

Repeat the above process recursively until NULL nodes are encountered.

Python Code for Recursive Approach

class TreeNode:
    '''
    Tree Node
    '''
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.max = 0
    def Diameter(self, root: TreeNode) -> int:
        if root is None: return 0
        def traverse(root):
            if root is None: return 0
            left = traverse(root.left)
            right = traverse(root.right)
            if left + right > self.max:
                self.max = left+right
            return max(left, right) + 1
        traverse(root)
        return self.max

if __name__ == '__main__':
    root = TreeNode(10)
    root.left = TreeNode(11)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(31)
    root.right = TreeNode(12)

    print(Solution().Diameter(root))

 

Output

3

 

Time Complexity

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

1) Starting from the root node, find the farthest node in the binary tree using the DFS algorithm

2) Consider this farthest node as the initial node of the diameter of the binary tree

3) Again, using the DFS algorithm, calculate the farthest node from the initial node found in step 2.

4) Newly found farthest node will be the end node of the diameter of binary tree

 

Python Code for Iterative Approach

from collections import deque

class TreeNode:
    '''
    Tree Node
    '''
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
     def Diameter(self , root: TreeNode ):
        '''
        Function to find depth of the Binary Tree
        :param root: Root Node
        :return: Depth of the tree
        '''
        stack = deque ( [ root ] )
        depth = {None : 0}
        ans = 0
        while stack :
            node = stack.pop ()
            if not node :
                continue

            LDepth = depth.get ( node.left , None )
            RDepth = depth.get ( node.right , None )
            if LDepth== None or RDepth == None :
                stack.append ( node )
                stack.append ( node.left )
                stack.append ( node.right )
                continue

            depth [ node ] = max ( LDepth, RDepth ) + 1
            ans = max ( LDepth+ RDepth , ans )

        return ans
if __name__ == '__main__':
    root = TreeNode(10)
    root.left = TreeNode(11)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(31)
    root.right = TreeNode(12)

    print(f'Diameter is : {Solution().Diameter(root)}')

 

Output

Diameter is : 3

 

Time Complexity

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

Conclusion

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. 

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Shivali Bhadaniya
I'm Shivali Bhadaniya, a computer engineer student and technical content writer, very enthusiastic to learn and explore new technologies and looking towards great opportunities. It is amazing for me to share my knowledge through my content to help curious minds.