543. Diameter of Binary Tree

Dhanaraj S
1 min readApr 7, 2022

Check out the problem description here

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)

--

--

Dhanaraj S

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.