# Binary Tree Diameter

Given 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. This not necessarily means that the path starts from the root node.

## Recursive approach

We are going to use recursion and Depth First Search to solve this problem. The algorithm is simple and straight forward.

1. At any given time, we are going to calculate the `height`, `diameter` and `currentDiameter` of the Binary Tree.
2. The `base` case will be if there is `!tree`, that is we have reached one level deeper than the root node. There, the height and diameter will always be `0`. We return `new TreeInfo(0, 0)` from there. Representing height and diameter of the tree at that point in time.
3. We then traverse the `left` subtree and the `right` subtree.
4. The `longest path from root` will be the `height of left subtree + height of right subtree`.
5. The `Maximum Diameter` will be the `MAXIMUM` of `left subtree diameter` and `right subtree diameter`.
6. The `Current Diameter` will be the `MAXIMUM` of the `longest path from root` and the `maximum diameter so far`.
7. The `Current height` is calculated by taking the `MAXIMUM` of `current diameter` and `maximum diameter` adding `1` to it to account for the current node that we are looking at. This ensures we always get the maximum value possible for the diameter.
8. At the end, we return the `TreeInfo` object with `currentDiameter` and `currentHeight`. Return the diameter from here.

### Time complexity

• `O(n)` because we are performing Depth First Search and every node has to be traversed atleast once.
Solve Binary Tree Diameter on Algochurn

## Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn