# 543. Diameter of Binary Tree

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)

--

--

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