543. Diameter of Binary Tree

Check out the problem description here

Diameter of Binary Tree - LeetCode

Solution

Diameter of the tree is the number of edges of longest path between 2 nodes in the tree.

Approach 1:

Visit all nodes, and for each node find its right height and left height and add both of them to get the diameter passing through that node. This is done for all nodes and maximum of among them is chosen as the diameter of the entire tree

find_max(node):
 if root ==None :
   return 
 left_height = height_fun(node.left)
 right_height =height_fun(node.right)
depth_max = max(depth_max,left_height  +right_height)
 find_max(node.left)
 find_max(node.right)

Time :O(n²)

Space :O(n)

Approach2:

More time efficient solution

class Solution:
    
    def diameterOfBinaryTree(self,root):
        self.max_=0
        self.rec(root)
        return self.max_
    def rec(self,node):
        if not node:
            return 0
        left = self.rec(node.left)
        right = self.rec(node.right)
        self.max_=max(self.max_,left+right)
        return max(left,right)+1

Time :O(n)

Space :O(n)