This post is completed by 3 users
|Add to List
134. Diameter Of a Binary Tree
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 the left subtree.
- Find the height of the right subtree.
- Find the left diameter.
- Find the right diameter.
- Return the Maximum(Diameter of left subtree, Diameter of right subtree, the Longest path between two nodes which passes through the root.)
Time Complexity: Since when calculating the diameter, every iteration for every node, is calculating the height of the 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 the tree and diameter in the same iteration.
Every node will return the two pieces of information in the same iteration, the height of that node and the diameter of the tree with respect to that node.
Output: Diameter of Tree 6