Diameter of Binary Tree easy

Problem Statement

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

Steps

1. Depth-First Search (DFS): We'll use a recursive DFS approach to traverse the tree.
2. Diameter Calculation: For each node, we calculate the maximum depth of its left and right subtrees. The diameter passing through that node is the sum of these depths.
3. Maximum Diameter: We maintain a global variable maxDiameter to track the maximum diameter encountered so far.
4. Recursive Function: The recursive function returns the maximum depth of the subtree rooted at the current node. It also updates maxDiameter during each call.

Explanation

The key idea is that the diameter of a tree might not pass through the root. Therefore, we need to explore all paths. Our DFS approach efficiently explores all paths by calculating the depth of the left and right subtrees for each node and using the sum of these depths to compute the diameter at that node. The maximum diameter encountered during the traversal is the final answer.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDiameter = 0;

    int maxDepth(TreeNode* node) {
        if (node == nullptr) return 0;

        int leftDepth = maxDepth(node->left);
        int rightDepth = maxDepth(node->right);

        maxDiameter = max(maxDiameter, leftDepth + rightDepth); // Update maxDiameter

        return 1 + max(leftDepth, rightDepth); //Return the max depth of subtree
    }

    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root); // Call to initiate the recursive process
        return maxDiameter;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the DFS traversal.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack, which in the worst case (a skewed tree) can be as large as the height of the tree. In the best case (a balanced tree), the space complexity would be O(log N).