Given a binary tree, the task is to find it's **diameter** or **width**.

The **diameter** or **width** of a tree is the number of nodes on the longest path between two end nodes.

##### Example 1: Diameter of a Binary Tree

Input:

**Output: **7

## Solutions

### Method 1: Recursion

The diameter of a tree T is the largest of the following quantities:

**1)** the diameter of T's left subtree.

**2)** the diameter of T's right subtree.

**3)** the longest path between leaves that goes through the root of T (heightOfLeft + heightOfRight + 1)

##### Complexity

The time complexity of this solution is

**O(n**and space complexity is also^{2})**O(n)**for call stack.### Method 2: Recursion in O(n)

The diameter of a node is nothing but **"1 + leftHeight + rightHeight"** and diameter of a tree is the max diameter of any node in the tree.

The idea is to calculate **diameter (1 + leftHeight + rightHeight)** of every node in "height" function itself and update "max diameter so far (d)".

##### Complexity

The time complexity of this solution is

**O(n)**and space complexity is also**O(n)**for call stack.