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.
We are going to use recursion and Depth First Search to solve this problem. The algorithm is simple and straight forward.
currentDiameterof the Binary Tree.
basecase 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.
leftsubtree and the
longest path from rootwill be the
height of left subtree + height of right subtree.
Maximum Diameterwill be the
left subtree diameterand
right subtree diameter.
Current Diameterwill be the
longest path from rootand the
maximum diameter so far.
Current heightis calculated by taking the
1to it to account for the current node that we are looking at. This ensures we always get the maximum value possible for the diameter.
currentHeight. Return the diameter from here.
O(n)because we are performing Depth First Search and every node has to be traversed atleast once.