Objective: – Given a binary tree, write an algorithm to find the diameter of the tree.
What is Diameter Of a Tree: Diameter of tree is defined as A longest path or route between any two nodes in a tree. The path may or may not for through the root.
Diameter of a tree w.r.t root can be defined as
Maximum(Diameter of left subtree, Diameter of right subtree, Longest path between two nodes which passes through the root.)
Now the diameter of left and right subtree’s can be solved recursively. And Longest path between two nodes which passes through the root can be calculated as 1 + height of left subtree + height of right subtree.
Please read this post to know how to find the Height of a tree.
We will explain Two approaches , First one will be Naive approach -O(N2) and then we will improve it to O(N).
- Find the height of left subtree.
- Find the height of right subtree.
- Find the left diameter.
- Find the right diameter.
- Return the Maximum(Diameter of left subtree, Diameter of right subtree, Longest path between two nodes which passes through the root.)
Time Complexity: Since when calculating the diameter, every iteration for every node, is calculating height of tree separately in which we iterate the tree from top to bottom and when we calculate diameter recursively so its O(N2)
Output: Diameter of Tree: 6
Now we will improve it further. If you notice at every node to find the diameter we are calling a separate function to find the height. We can improve it by finding the height of tree and diameter in the same iteration.
Every node will return the two information in the same iteration , height of that node and diameter of tree with respect to that node.
Output: Diameter of Tree 6