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) =
5Returns (int)
3Example 2
Input
tree (int[]) =
[1,2]size (int) =
2Returns (int)
1Example 3
Input
tree (int[]) =
[1]size (int) =
1Returns (int)
0Use 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)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run