Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
Intermediate Level

Implement the diameterOfBinaryTree method that returns the diameter length of a binary tree.

The input contains a binary tree represented as an integer array tree in level-order format.

Your task is to return the diameter of the binary tree. The diameter is the number of edges in the longest path between any two nodes in the tree.

The longest path may pass through the root, but it does not have to.

Example 1
Input:
tree (int[]) = [1,2,3,4,5]
size (int) = 5
Return:
(int) 3
Example 2
Input:
tree (int[]) = [1,2]
size (int) = 2
Return:
(int) 1
Example 3
Input:
tree (int[]) = [1]
size (int) = 1
Return:
(int) 0

Use depth-first search to calculate subtree heights and update the best diameter.

For every node, the longest path passing through that node is leftHeight + rightHeight. Keep the maximum value found while recursively calculating heights.

The height returned by a node is 1 + max(leftHeight, rightHeight), but the final answer is the best diameter measured in edges.

Pseudocode:

function diameterOfBinaryTree(tree, size):
    best = 0
    height(0)
    return best
function height(index):
    if index >= size or tree[index] is missing:
        return 0
    leftHeight = height(2 * index + 1)
    rightHeight = height(2 * index + 2)
    best = max(best, leftHeight + rightHeight)
    return 1 + max(leftHeight, rightHeight)
Run your code to see the result.