Diameter of a Binary Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
Solution:
- The diameter of a tree T is the largest of the following quantities:
- the diameter of T’s left subtree
- the diameter of T’s right subtree
- the longest path between leaves that goes through the root of T
Algorithm:
- Traverse tree in PostOrder
- If node is null then
- return 0
- diameterOfLeftSubTree = recursively call with node.left
- diameterOfRightSubTree = recursively call with node.right
longestPathBetweenLeaves = heightOfLeftSubTree + heightOfRightSubTree + 1
return max (diameterOfLeftSubTree, diameterOfRightSubTree, longestPathBetweenLeaves)
- If node is null then
Time Complexity: O(n^2)
Latest Source Code:
Github: BinaryTreeMaxWidthFinder.java
Output:
1 / \ / \ / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 5 / / / / 8 6 \ 7 Diameter : 6 1 / \ / \ / \ / \ 2 3 / \ / \ 4 5 / \ 6 7 Diameter : 6