Given a BST, write a function to return its diameter. The diameter of a Binary Tree is defined as the "Number of nodes on the longest path between two leaf nodes".

Check out**Use Me** section to learn about the helper methods.

Example:

20

/ \

15 30

/ \ \ diameter ==> 7

14 18 35

/ \ /

17 19 32

Check out

Need a **hand?** Try out these hints, one at a time.

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

Go through each node of the tree and find the maximum of the following three values at each step

1) Diameter of the left subtree

2) Diameter of the right subtree

3) Height of the left subtree + height of the right subtree + 1

1) Diameter of the left subtree

2) Diameter of the right subtree

3) Height of the left subtree + height of the right subtree + 1

1. Create a helper function which returns the diameter and height of the root node.

2. Find the diameter of the left and right subtrees using recursion,

3. Height of the root node is

4. The diameter of the root node is

5. Return the height and finalDiameter as below.

`public int[] diameterAndHeight`

`(TreeNode root )`

2. Find the diameter of the left and right subtrees using recursion,

`int[] leftResult = diameterAndHeight`

`(root.left)`

`int[] rightResult = diameterAndHeight`

`(root.right)`

`leftDiameter = leftResult[0];`

`rightDiameter = rightResult[0];`

3. Height of the root node is

`height =`

`Math.max(leftResult[1], rightResult[1])`

`+ 1`

4. The diameter of the root node is

`rootDiameter = leftResult[1]`

`+ rightResult[1] + 1`

5. Return the height and finalDiameter as below.

`finalDiameter = Math.max(rootDiameter,`

`Math.max(leftDiameter, rightDiameter));`

`heightDiameter[0] = finalDiameter;`

`heightDiameter[1] = height;`

`return heightDiameter`

public int diameter(TreeNode root) { }

**C**

**Java**

**Python**