Given a binary tree, the task is to find it's diameter or width.
The diameter or width of a tree is the number of nodes on the longest path between two end nodes.
Example 1: Diameter of a Binary Tree
Input:
Output: 7
Solutions
Method 1: Recursion
The diameter of a tree T is the largest of the following quantities:
1) the diameter of T's left subtree.
2) the diameter of T's right subtree.
3) the longest path between leaves that goes through the root of T (heightOfLeft + heightOfRight + 1)
Complexity
The time complexity of this solution is O(n2) and space complexity is also O(n) for call stack.
Method 2: Recursion in O(n)
The diameter of a node is nothing but "1 + leftHeight + rightHeight" and diameter of a tree is the max diameter of any node in the tree.
The idea is to calculate diameter (1 + leftHeight + rightHeight) of every node in "height" function itself and update "max diameter so far (d)".
Complexity
The time complexity of this solution is O(n) and space complexity is also O(n) for call stack.