Diameter of a Binary Tree

In this class, We discuss the Diameter of a Binary Tree

Readers can prepare an entire competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary tree.

Our task is to identify the diameter of the binary tree.

Example:

The below diagram shows the diameter of the binary tree.

The diameter is the longest path between two end nodes.

Logic:

In our last class, we discussed height-balanced binary trees or not.

The same logic we use here.

In height balance, each function returns the height of the left and right sub-trees.

We use the same logic to return the height.

We maintain a maximum diameter global variable.

We find the diameter at each function. And keeps updating the maximum diameter variable.

The step-by-step explanation is provided in the video.

Code:

class Node:

    # Constructor to create a new node

    def __init__(self, val):

        self.data = val

        self.left = None

        self.right = None

class Solution:

    def findheight(self,root):

        if root==None:

            return 0

        ls=self.findheight(root.left)

        rs=self.findheight(root.right)

        self.gmax=max(self.gmax,ls+rs+1)

        maxsubtree=max(ls,rs)+1

        return maxsubtree

    #Function to return the diameter of a Binary Tree.

    def diameter(self,root):

        # Code here

        self.gmax=0

        self.findheight(root)

        return self.gmax

if __name__ == ‘__main__’:

    root = Node(1)

    root.left = Node(2)

    root.right = Node(3)

    root.left.left = Node(4)

    root.left.right = Node(5)

    root.right.left = Node(6)

    root.right.right = Node(7)

    root.right.left.right = Node(8)

    root.right.right.right = Node(9)

    print(“Diameter of a binary tree”)

    ob=Solution()

    z=ob.diameter(root)

    print(z)