Here is solutions for Diameter of Binary Tree.

1. Understand the problem

• You’re given a binary tree, and you must compute its diameter.

• Diameter of a binary tree = The length (number of edges) of the longest path between any two nodes in the tree.

• Important notes:

  • The longest path may or may not pass through the root.

  • Path length = number of edges, not number of nodes.

  • If the tree is empty, diameter = 0.

  • A single node tree also has diameter = 0 (no edges)

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. How is the diameter measured? In nodes or edges?

=> LeetCode measures edges, not nodes.

1. Can the tree be empty? What is the expected result?

=> Yes. Diameter should be 0.

1. Tree size constraints?

=> Usually up to 10^4 nodes → recursion depth is safe but iterative may be needed rarely.

1. Are node values relevant?

=> No. Only structure matters.

1. What about skewed trees (like a linked list)?

=> Diameter = number of edges = n - 1.

3. Explore examples.

• Example 1:

      1
     / \
    2   3
   / \
  4   5

• Longest Path: 4 -> 2 -> 1 -> 3, diameter = 3 edges.

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Naive Approach - Time O(N^2), Space O(H), worst case O(N)

The final diameter for this node is the maximum of:

- diameter through this node

- diameter in left subtree

- diameter in right subtree

Then recursively compute diameter of children.

• Time: O(N^2) = N * O(N)

• Space: O(H), worst case O(N).

4.2. Solution 2: Optimized DFS - Time O(N), Space O(H), worst case O(N)

Key idea

- Perform one DFS and compute:

For each node:

height = 1 + max(left height, right height)
update global diameter = max(diameter, left height + right height)

• Time: O(N).

• Space: O(H), worst case O(N).

4.3. Solution 3: Iterative DFS with Stack - Time O(N), Space O(N) but only stack

• Post-order traversal using a stack:

  • Track heights using a hashmap

  • Compute diameter the same way as recursive solution

• Time: O(N).

• Space: O(N) stack.

5. Implement solutions.

5.1. Naive Solution - Time O(N^2), Space O(H)

The final diameter for this node is the maximum of: Max at this root, can be max from 2 leaf of the left or right tree.

• diameter through this node

• diameter in left subtree

• diameter in right subtree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        leftHeight = self.maxHeight(root.left)
        rightHeight = self.maxHeight(root.right)
        diameter = leftHeight + rightHeight
        sub = max(self.diameterOfBinaryTree(root.left),
                  self.diameterOfBinaryTree(root.right))
        return max(diameter, sub)


    def maxHeight(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.maxHeight(root.left), self.maxHeight(root.right))

• Time: O(N^2) = Get Height O(N), Recursive O(N) ~ O(N^2).

• Space: O(H), worst case O(N).

5.2. DFS Recursion - Use res - Time O(N), Space O(H)

• Use the idea:

  • Use res value to store the maximum value => Instead of re-computing new height each visit, store it in left and right => Each node value max = curr_node (1) + max(height[left], height[right]) => Recursive to calling it
  • Max of the node based on the left and right height.

# Recursive calling
left = dfs(root.left)
right = dfs(root.right)
res = max(res, left + right)

# Return value
return 1 + max(left, right)

• Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root):
            nonlocal res

            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res

• Time: O(N).

• Space: O(H), worst case O(N).

5.3. Iterative DFS - Use mp to store the previous value, Idea same memorization of DP - Time O(N), Space O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        stack = [root]
        mp = {None: (0, 0)}

        while stack:
            node = stack[-1]

            if node.left and node.left not in mp:
                stack.append(node.left)
            elif node.right and node.right not in mp:
                stack.append(node.right)
            else:
                node = stack.pop()

                leftHeight, leftDiameter = mp[node.left]
                rightHeight, rightDiameter = mp[node.right]

                mp[node] = (1 + max(leftHeight, rightHeight),
                           max(leftHeight + rightHeight, leftDiameter, rightDiameter))

        return mp[root][1]

• Time: O(N).

• Space: O(N).

6. Dry run testcases.

      1
     / \
    2   3
   / \
  4   5

…