Binary Tree Diameter
Given the root to a Binary Tree, Return an integer that represents the diameter of the Binary Tree.
A Diameter is the length of the longest path in the Binary Tree.
Note: This not necessarily means that the path starts from the root node.
Example
Input Binary Tree
Output
Output = 6
Explanation
The longest path in the binary tree is 9->8->7->3->4->5->6. The number of edges are 6. Hence, the diameter of the Binary Tree is 6.
The orange color highlight denotes the path of the diameter of the Binary Tree.
Constraints
1 <= Nodes <= 1000
Stuck? Check out hints
Click to reveal
Can you try using any tree traversal algorithms like Depth First Search and Breadth First Search? Which algorithm makes more sense in this case?
Click to reveal
To get the diameter, you need to calculate the height of the tree/node you're currently at. Try traversing to the end of the tree and return from there. At the leaf node, the height of the tree is always 0.