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 easy

0. Why / judgment (K3)

Family: Tree DP / dual DFS · longest path

Diameter = longest path between any two nodes (here often counted in nodes or edges — match problem statement!). DFS returns height; at each node update diameter with left_height+right_height (+1 if nodes). Or two-BFS: from any node to farthest, then farthest again — works on general trees.

1. Pattern + recognition + when-NOT (K12)

Pattern / template: Global best; dfs(node)->height; best=max(best, hL+hR); return 1+max(hL,hR). Recognition: longest path in tree.

When-NOT: Not min depth. Not binary-tree-only required (dual BFS generalizes). Not graph with cycles (then longest path NP-hard). Watch nodes vs edges counting off-by-one.

2. Complexity derivation (K11)

O(n) time, O(h) space recursive / O(n) BFS.

3. Edge hand-run (K13)

Two nodes: diameter 2 nodes / 1 edge.
Line of 4: diameter 4 nodes.
Star: diameter 2 edges through center.
Single node: 1 or 0 per definition.

4. Interviewer follow-ups & drills

Q1. Why height sum at node?
Model answer: Best path through node joins deepest leaves in two subtrees.

Q2. Dual BFS proof sketch?
Model answer: Farthest from u is an endpoint of some diameter.

Q3. Mis-tag max depth only?
Model answer: Max depth is one arm; diameter needs two arms.

✅ 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

0. Why / judgment (K3)

Family: DFS heights with global best

Post-order heights ensure children done. Update global before return. Clarify units: if problem says number of nodes on path, diameter_nodes = hL+hR+1.

1. Pattern + recognition + when-NOT (K12)

Pattern / template: Tree DP height; track best path.

When-NOT: All-pairs Floyd O(n³) insane for trees.

2. Complexity derivation (K11)

Θ(n)/Θ(h).

3. Edge hand-run (K13)

Hand-run node path 1-2-3-4 line: at 2, heights combine growing; final nodes=4.
Balanced small: root with two leaves — nodes diameter 3.

4. Interviewer follow-ups & drills

Q1. Edges vs nodes?
Model answer: edges = nodes-1 on simple path; match statement.

Q2. Binary only code on n-ary?
Model answer: Loop children take top-2 heights.

Q3. Hostile recursion depth?
Model answer: Iterative postorder or dual BFS.

🧩 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

← Minimum Time to Type Word Using Sp Maximum Number of Balloons →