Tree diameter - PrismoSkills
Solution: Note that the diameter may not pass through the root-node (as shown above)
Also, the ends of the diameter will be such that one of them lies in the
left subtree of a node and the other end lies in the right subtree of the same node.
Otherwise the diameter will tend to appear like a knot.
For example, if the diameter of the above tree were to be: 9 -> 14 -> 7 -> 14 -> 22,
then 14 -> 7 -> -> 14 nodes would appear like a knot and that is not allowed to be in a diameter.
So, there will be one node whose left and right legs of deepest height would form the diameter.
Our task is to find that node for which 1 + diameter(left) + diameter(right) is the maximum.
But there's always room for optimization!!
See the calls to depth() function.
At every node, depth() is called and same nodes are being traversed multiple times due to this.
To optimize, we can do either of these:
Return height also from the diameter() function by changing the return type to Pair<Integer, Integer>
Store height for each node in the tree itself and calculate it only once before calling diameter.
Read full article from Tree diameter - PrismoSkills
Solution: Note that the diameter may not pass through the root-node (as shown above)
Also, the ends of the diameter will be such that one of them lies in theleft subtree of a node and the other end lies in the right subtree of the same node.
Otherwise the diameter will tend to appear like a knot.
For example, if the diameter of the above tree were to be: 9 -> 14 -> 7 -> 14 -> 22,
then 14 -> 7 -> -> 14 nodes would appear like a knot and that is not allowed to be in a diameter.
So, there will be one node whose left and right legs of deepest height would form the diameter.
Our task is to find that node for which 1 + diameter(left) + diameter(right) is the maximum.
But there's always room for optimization!!
See the calls to depth() function.
At every node, depth() is called and same nodes are being traversed multiple times due to this.
To optimize, we can do either of these:
Return height also from the diameter() function by changing the return type to Pair<Integer, Integer>
Store height for each node in the tree itself and calculate it only once before calling diameter.
Read full article from Tree diameter - PrismoSkills
