Binary Tree Diameter

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.