# Problem

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the **longest** path between any two nodes in a tree. This path may or may not pass through the root.

**Example:**

Given a binary tree

1 / \ 2 3 / \ 4 5

Return **3**, which is the length of the path [4,2,1,3] or [5,2,1,3].

**Note:** The length of path between two nodes is represented by the number of edges between them.

The length of the diamer of the binary tree can pass through the root of the binary tree or not.

In case that it passes.

The diameter is the height of the left subtree + the height of right subtree + 1 that is the root.

**height of the left subtree + the height of right subtree + 1**

is it not necesary that the path of the diameter passes throught the root.

In case that it dosn’t passes.

You need to calculate the diameter of the left and right subtree and the right subtree.

Now lets consider the new tree, for the new tree

**ldiameter**will be the height of the left subtree. and repeat for**rdiameter.**if it does not pass throught root we need to pass the left subtree and right subtree through the recursive function. and out of that leftsubtree and right rubstring reconsider the greater and pick that one.

height of the left subtree + the height of right subtree + 1,max (ldiameter, rdiameter) )

you have to calculate both of this scenarios because we are not sure wheter or not we pass throught the root.

max(height of the left subtree + the height of right subtree + 1,max (ldiameter, rdiameter) ))

# solution

/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init(_ val: Int) { * self.val = val * self.left = nil * self.right = nil * } * } */ class Solution { func diameterOfBinaryTree(_ root: TreeNode?) -> Int { guard root != nil else{return 0} return diameter(root: root) } func diameter(root: TreeNode?) -> Int { guard root != nil else{return 0} var rootDiameter:Int = heightOfBinaryTree(root: root?.left) + heightOfBinaryTree(root: root?.right) + 1 print("\(rootDiameter)") var leftDiameter:Int = diameter(root: root?.left) var rightDiameter:Int = diameter(root: root?.right) return max(rootDiameter, max(leftDiameter, rightDiameter)) } func heightOfBinaryTree(root: TreeNode?) ->Int { if(root == nil){ return 0 }else{ return max(heightOfBinaryTree(root: root?.left), heightOfBinaryTree(root: root?.left)) + 1 } } }

reference

https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/529/week-2/3293/