easy Tree Diameter

Problem Statement

Given a binary tree, find the length of its diameter. The diameter of a tree is the number of nodes on the longest path between any two leaf nodes. The diameter of a tree may or may not pass through the root.

Note: You can always assume that there are at least two leaf nodes in the given tree.

Constraints:

n == edges.length + 1
1 <= n <= 10⁴
0 <= a_i, b_i < n
a_i != b_i

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Tree Diameter (problem)

1. Why / judgment

Longest path between leaves (or nodes). Recognition: need heights of both children at every node + global max — single post-order DFS, not two BFS from arbitrary roots (though two-BFS works on unweighted trees too).

2. Worked complexity (K11)

Optimal DFS: Θ(n) time, O(h) stack.
Naive: for each node as root recompute — worse constants / easy to get O(n²).
Clarify edges vs nodes in the answer.

3. Pattern + when-NOT (K12)

Name: DIAMETER / LONGEST PATH IN TREE

When-NOT: Only max depth from root. Weighted edges need different DP.

4. Edges (K13)

≥2 leaves assumed here. Single edge tree. Diameter not through root.

5. Panel

Q1. Must path include root? A: No.

Q2. Time lower bound? A: Ω(n) — every node can affect.

Q3. Two-BFS method? A: From any node find farthest u; from u find farthest v; dist(u,v) is diameter (tree property).

✅ Solution Tree Diameter

Problem Statement

Note: You can always assume that there are at least two leaf nodes in the given tree.

Constraints:

n == edges.length + 1
1 <= n <= 10⁴
0 <= a_i, b_i < n
a_i != b_i

Solution

This problem follows the Binary Tree Path Sum pattern. We can follow the same DFS approach. There will be a few differences:

At every step, we need to find the height of both children of the current node. For this, we will make two recursive calls similar to DFS.
The height of the current node will be equal to the maximum of the heights of its left or right children, plus ‘1’ for the current node.
The tree diameter at the current node will be equal to the height of the left child plus the height of the right child plus ‘1’ for the current node: diameter = leftTreeHeight + rightTreeHeight + 1. To find the overall tree diameter, we will use a class level variable. This variable will store the maximum diameter of all the nodes visited so far, hence, eventually, it will have the final tree diameter.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

java

// class TreeNode {
//   int val;
//   TreeNode left;
//   TreeNode right;

//   TreeNode(int x) {
//     val = x;
//   }
// };

public class Solution {

  private int treeDiameter = 0;

  public int findDiameter(TreeNode root) {
    treeDiameter = 0;
    calculateHeight(root);
    return treeDiameter;
  }

  private int calculateHeight(TreeNode currentNode) {
    if (currentNode == null) return 0;

    int leftTreeHeight = calculateHeight(currentNode.left);
    int rightTreeHeight = calculateHeight(currentNode.right);

    // if the current node doesn't have a left or right subtree, we can't have
    // a path passing through it, since we need a leaf node on each side
    if (leftTreeHeight != 0 && rightTreeHeight != 0) {
      // diameter at the current node will be equal to the height of left subtree +
      // the height of right sub-trees + '1' for the current node
      int diameter = leftTreeHeight + rightTreeHeight + 1;

      // update the global tree diameter
      treeDiameter = Math.max(treeDiameter, diameter);
    }

    // height of the current node will be equal to the maximum of the heights of
    // left or right subtrees plus '1' for the current node
    return Math.max(leftTreeHeight, rightTreeHeight) + 1;
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.right.left = new TreeNode(5);
    root.right.right = new TreeNode(6);
    Solution sol = new Solution();
    System.out.println("Tree Diameter: " + sol.findDiameter(root));
    root.left.left = null;
    root.right.left.left = new TreeNode(7);
    root.right.left.right = new TreeNode(8);
    root.right.right.left = new TreeNode(9);
    root.right.left.right.left = new TreeNode(10);
    root.right.right.left.left = new TreeNode(11);
    System.out.println("Tree Diameter: " + sol.findDiameter(root));
  }
}

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).

🎯 STRICT STANDOUT — Solution Tree Diameter

1. Why / judgment

Diameter is height DFS + global max, not the Path Sum pattern. At each node, candidate path uses both side heights; better candidates may lie entirely in a subtree — hence a global variable. Path may not pass through the root.

2. Worked complexity (K11)

Nodes convention (this page): height(null)=0; height(u)=1+max(hL,hR);
cand = hL+hR+1 when both sides non-zero; treeDiameter = max(...).
One DFS → Θ(n) time, O(h) stack (skewed O(n)).
Edges convention (LC 543): cand=hL+hR; return 1+max — state which.
Example 1(2(4),3(5,6)): through 1: hL=2,hR=2 → diam nodes 5; verify offline.

3. Pattern + when-NOT (K12)

Name: DIAMETER = HEIGHT DFS + GLOBAL MAX

When-NOT: Max depth alone (misses bent paths). Path Sum I (target to leaf). APSP overkill on trees.

4. Edges (K13)

Two nodes: diam 2 (nodes) / 1 (edges). V-shape root with two leaves: 3 nodes.
Line of n: diameter n (nodes). null: 0 if allowed.

5. Panel

Q1. Why global? A: Best path may be entirely in a subtree.

Q2. Stack space? A: O(h); skewed O(n).

Q3. Relation to LCA? A: Diameter endpoints' LCA is the highest node on the diametral path — different algorithm family.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Tree Diameter? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Tree Diameter** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Tree Diameter** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Tree Diameter**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Tree Diameter**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Balanced Binary Tree Maximum Depth of N-ary Tree →