Tree Diameter

Problem

Return the diameter of a binary search tree built from the given values, measured in edges.

Insert values in order (duplicates ignored). For every node compute the heights of its left and right subtrees; the diameter is the largest sum of those two heights over all nodes.

Return the diameter. An empty tree or a single node has diameter 0.

Hint

The longest path through a node is the sum of its left and right subtree heights.

Test cases

case 1

in: [[5,3,8,1,4,7,9]]

expected: 4

case 2

in: [[1,2,3]]

expected: 2

case 3

in: [[5]]

expected: 0

case 4

in: [[]]

expected: 0

Starter codePython

def tree_diameter(values):
    # Your code here
    pass

4 test cases · run your code against them in the editor