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 to Solve

1. Depth-First Search (DFS): We will use a recursive DFS approach to traverse the tree.
2. Height Calculation: For each node, we need to calculate its height (the maximum distance from the node to a leaf node).
3. Diameter Calculation: The diameter at any node is the sum of the heights of its left and right subtrees. We keep track of the maximum diameter encountered so far.
4. Return Value: The function will return the maximum diameter found during the traversal.

Explanation

The key insight is that the diameter might not pass through the root. Therefore, we need to explore all possible paths. We use a helper function dfs to recursively calculate the height of each subtree and simultaneously update the maximum diameter. For each node, the diameter passing through that node is the sum of the heights of its left and right subtrees. The global maximum diameter is updated accordingly during the traversal.

Code (C#)

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int maxDiameter = 0;

    public int DiameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return maxDiameter;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = dfs(node.left);
        int rightHeight = dfs(node.right);

        maxDiameter = Math.Max(maxDiameter, leftHeight + rightHeight); // Update max diameter

        return 1 + Math.Max(leftHeight, rightHeight); // Return height of current subtree
    }
}

Complexity Analysis

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