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:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2] Output: 1
Constraints:
[1, 104].-100 <= Node.val <= 100This approach uses a depth-first search (DFS) to calculate the diameter of the binary tree. The key idea is to determine the longest path passing through each node and update the maximum diameter accordingly.
By computing the height of the left and right subtrees at each node, we can obtain the potential diameter passing through that node as the sum of the heights plus one. We will keep track of the global diameter, updating it as necessary.
The implementation involves a helper function dfs that traverses the tree recursively. For each node, it calculates the height of the left and right subtrees. The diameter is updated as the maximum of the current diameter and the sum of the heights of the left and right subtrees. The function diameterOfBinaryTree initializes the diameter and invokes the DFS.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree, representing the call stack size due to recursion.
This method enhances the recursive DFS approach by incorporating memoization for subtree height calculations, thereby eliminating redundant computations and improving performance, especially beneficial for trees with high duplication of node structures.
Memoization is implemented using an auxiliary array memo, which stores the height of each node index as calculated by DFS to avoid redundant computations. TreeNode indexing assumes a complete binary tree structure for simplicity in accessing child indices.
C++
Java
Python
C#
JavaScript
Time Complexity: Approaches O(N) due to controlled redundant calculations via memoization.
Space Complexity: O(N) for storing the heights in the memo array.
| Approach | Complexity |
|---|---|
| Depth First Search | Time Complexity: O(N), where N is the number of nodes. Each node is visited once. |
| Dynamic Programming with Memoization | Time Complexity: Approaches O(N) due to controlled redundant calculations via memoization. |
L16. Diameter of Binary Tree | C++ | Java • take U forward • 438,921 views views
Watch 9 more video solutions →Practice Diameter of Binary Tree with our built-in code editor and test cases.
Practice on FleetCode