Algorithm-Day41-Diameter-of-Binary-Tree-lc-543

Posted on In , Views:

🧩 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. This path may or may not pass through the root.

Note: The length is measured by the number of edges between nodes.

💬 Example

1
2
Input: root = [1,2,3,4,5]
Output: 3

Explanation:

  • Longest path is [4 → 2 → 1 → 3], which has 3 edges.

💡 Approach: DFS with Depth Tracking

  • At each node, the longest path through that node is:
    leftDepth + rightDepth
  • We update a global maximum diameter during traversal.

🔢 Java Code (Recursive DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return diameter;
    }

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

        int left = depth(node.left);
        int right = depth(node.right);

        // Update global diameter
        diameter = Math.max(diameter, left + right);

        return 1 + Math.max(left, right);
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visit every node once
  • Space Complexity: O(h) — recursion stack, where h = height of tree

✍️ Summary

  • This problem is about recognizing the non-root longest path possibility.
  • Track the depths of subtrees and compute diameters along the way.
  • A great example of combining DFS + global tracking.

Pattern also appears in path sum and subtree depth problems. Master it well.