Diameter of Binary Tree
Problem Description
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Output: 1
Constraints:
- The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. Recursive Approach
The naive idea here is to consider each node of the binary tree, calculate the maximum path length traversing through it, and then take the largest of these lengths. The maximum path of a node is calculated as the sum of the heights of its left and right subtrees.
Intuition:
- Definition of Diameter: For every node we consider, its diameter is defined as the number of nodes on the longest path between two leaves.
- Height Calculation: The height of a node in this approach is determined by calculating the height of its left and right subtrees recursively.
- Brute Force Calculation: For each node, calculate the diameter (left height + right height), and update the maximum diameter found so far.
Code:
- Time Complexity: O(N^2), since for every node, we calculate the height of the tree, a O(N) operation.
- Space Complexity: O(N), space required for recursion stack in the worst case (skewed tree).
2. Optimized Recursive Approach
To optimize the naive approach, we can calculate the height of the tree while computing the diameter at the same time. This prevents re-calculation of the height, reducing redundant operations.
Intuition:
- Postorder Traversal: Utilize postorder traversal, where we calculate the height of subtrees and the diameter while backtracking.
- Passing the Max Diameter: Use a global or wrapper object to store the maximum diameter found during the traversal.
Code:
- Time Complexity: O(N), since we only pass through each node once.
- Space Complexity: O(N), due to recursion call stack (worst case for skewed tree).