grid47 Exploring patterns and algorithms
Sep 13, 2024
5 min read
Solution to LeetCode 543: Diameter of Binary Tree Problem
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, which may or may not pass through the root.
Problem
Approach
Steps
Complexity
Input: The input consists of the root of a binary tree, where each node is represented by a value and pointers to its left and right child nodes.
Example: Input: root = [1,2,3,4,5]
Constraints:
• The number of nodes in the tree is in the range [1, 10^4].
• -100 <= Node.val <= 100
Output: Return the length of the longest path between any two nodes in the tree. The path is measured by the number of edges between the nodes.
Example: Output: 3
Constraints:
• The output will be an integer representing the length of the longest path.
Goal: The goal is to calculate the diameter of the binary tree efficiently.
Steps:
• Perform a depth-first search (DFS) to traverse the tree.
• For each node, compute the maximum depth of its left and right subtrees.
• Track the maximum sum of the depths of the left and right subtrees, which gives the diameter.
Goal: The binary tree will have at least one node, and node values will be between -100 and 100.
Steps:
• The binary tree contains up to 10^4 nodes.
• Node values will range between -100 and 100.
Assumptions:
• The tree is a valid binary tree.
• The input tree will contain at least one node.
• Input: Input: root = [1,2,3,4,5]
• Explanation: In this example, the tree has a longest path between node 4 and node 3 through node 2 and node 1, which has a length of 3 edges.
Approach: We can compute the diameter of the binary tree using a depth-first search (DFS) traversal. For each node, we calculate the maximum depth of its left and right subtrees and update the diameter based on the sum of the depths.
Observations:
• This is a classic depth-first search problem where we need to compute the maximum depth of subtrees and track the longest path.
• By using DFS, we can calculate the maximum depth from each node and compute the diameter by updating the result with the sum of the depths of the left and right subtrees.
Steps:
• Define a helper function to compute the depth of a node while also updating the diameter.
• For each node, recursively compute the depth of its left and right subtrees.
• For each node, update the diameter based on the sum of the left and right subtree depths.
Empty Inputs:
• The tree will not be empty as per the problem constraints.
Large Inputs:
• Ensure the solution works efficiently for trees with up to 10^4 nodes.
Special Values:
• Handle cases with only one node in the tree, where the diameter will be 0.
Constraints:
• The tree contains up to 10^4 nodes.
intdiameterOfBinaryTree(TreeNode* root) {
int d =0;
dep(d, root);
return d;
}
intdep(int&d, TreeNode* node) {
if(node ==NULL) return0;
int l = dep(d, node->left);
int r = dep(d, node->right);
d = max(d, l + r);
return1+ max(l, r);
}
1 : Function Definition
intdiameterOfBinaryTree(TreeNode* root) {
Defines the `diameterOfBinaryTree` function, which takes the root of the binary tree as an argument and returns the diameter of the tree.
2 : Variable Initialization
int d =0;
Initializes a variable `d` to store the maximum diameter found during the traversal of the tree.
3 : Recursive Call
dep(d, root);
Calls the helper function `dep` with `d` and the root of the tree to compute the depth of the tree and update the diameter.
4 : Return Statement
return d;
Returns the computed diameter `d` of the binary tree.
5 : Function Definition
intdep(int&d, TreeNode* node) {
Defines the helper function `dep`, which calculates the depth of a node and updates the diameter based on the longest path from that node.
6 : Base Case
if(node ==NULL) return0;
Base case for the recursion: if the node is `NULL`, return 0 as its depth.
7 : Recursive Call (Left Subtree)
int l = dep(d, node->left);
Recursively calls `dep` for the left child of the current node to compute the depth of the left subtree.
8 : Recursive Call (Right Subtree)
int r = dep(d, node->right);
Recursively calls `dep` for the right child of the current node to compute the depth of the right subtree.
9 : Update Diameter
d = max(d, l + r);
Updates the diameter `d` if the sum of the left and right subtree depths (`l + r`) is larger than the current diameter.
10 : Return Depth
return1+ max(l, r);
Returns the depth of the current node as `1 + max(l, r)`, where `l` and `r` are the depths of the left and right subtrees, respectively.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because each node is visited once.
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h) due to the recursive call stack, where h is the height of the tree.
