Find the Diameter of a BST

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".

Example:  
      20                                  
    /     \                              
   15     30 
  /  \      \  diameter ==> 7                    
 14  18     35
    /  \    /
   17  19  32

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

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

Quick hint to get things rolling

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

A more detailed explanation

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

Final hint! You should be able to code the problem on viewing this.

1. Create a helper function which returns the diameter and height of the root node.
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) {
    



}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Find the Diameter of a BST

Quick hint to get things rolling

A more detailed explanation

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :