Diameter of Binary Tree in DSA Python

Mental Model

The diameter is the longest path between any two nodes in a tree, which may or may not pass through the root.

Analogy: Imagine a network of roads connecting cities (nodes). The diameter is the longest possible route you can drive without repeating roads, possibly passing through the central city or not.

      1
     / \
    2   3
   / \
  4   5

Here, arrows show parent to children connections.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Calculate height of node 4 (leaf)

4 -> null (height=0)

Why: Leaf nodes have height 0, base case for recursion

Step 2: Calculate height of node 5 (leaf)

5 -> null (height=0)

Why: Leaf nodes have height 0, base case for recursion

Step 3: Calculate height of node 2 using children 4 and 5

2 -> 4 (height=0), 5 (height=0), so height=1

Why: Height is max child height + 1

Step 4: Calculate height of node 3 (leaf)

3 -> null (height=0)

Why: Leaf node height is 0

Step 5: Calculate height of node 1 using children 2 and 3

1 -> 2 (height=1), 3 (height=0), so height=2

Why: Height is max child height + 1

Step 6: Calculate diameter at node 2: left height + right height + 2 = 0 + 0 + 2 = 2

Diameter at 2 is 2

Why: Longest path through node 2 is from 4 to 5

Step 7: Calculate diameter at node 1: left height + right height + 2 = 1 + 0 + 2 = 3

Diameter at 1 is 3

Why: Longest path through node 1 is from 4 to 3

Step 8: Compare diameters and select max: max(2, 3) = 3

Final diameter is 3 edges

Why: Diameter is the longest path in the tree

Result:

Diameter path length = 3 edges (nodes 4 -> 2 -> 1 -> 3)

Annotated Code

DSA Python

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: TreeNode) -> int:
        self.diameter = 0

        def height(node):
            if not node:
                return -1  # height of null is -1 to count edges
            left_height = height(node.left)  # height of left subtree
            right_height = height(node.right)  # height of right subtree
            # update diameter at this node
            self.diameter = max(self.diameter, left_height + right_height + 2)
            return max(left_height, right_height) + 1  # height of current node

        height(root)
        return self.diameter

# Driver code to test the example
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

sol = Solution()
print(sol.diameterOfBinaryTree(root))

if not node: return -1 # height of null is -1 to count edges

base case returns -1 so leaf node height is 0 (edges count)

left_height = height(node.left) # height of left subtree

recursively find left subtree height

right_height = height(node.right) # height of right subtree

recursively find right subtree height

self.diameter = max(self.diameter, left_height + right_height + 2)

update diameter with longest path through current node

return max(left_height, right_height) + 1 # height of current node

return height of current node for parent's calculation

Output

3

Complexity Analysis

Time: O(n) because we visit each node once to calculate height and update diameter

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach might calculate height repeatedly causing O(n^2) time; this approach calculates height once per node

Edge Cases

Empty tree (root is None)

Diameter is 0 because no nodes exist

DSA Python

if not node:
    return -1  # height of null is -1 to count edges

Single node tree

Diameter is 0 because no edges exist

DSA Python

if not node:
    return -1  # height of null is -1 to count edges

Tree with only left or right children (skewed tree)

Diameter equals height of the tree (longest path is along the skew)

DSA Python

self.diameter = max(self.diameter, left_height + right_height + 2)

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern by combining subtree heights to find longest paths through nodes.

Common Mistakes

Mistake: Returning node count instead of edge count for diameter
Fix: Use height definition as edges (return -1 for null) so diameter counts edges correctly

Mistake: Calculating height multiple times causing slow performance
Fix: Calculate height once per node and update diameter during the same recursion

Summary

Finds the longest path between any two nodes in a binary tree measured in edges.

Use when you need the maximum distance between nodes in a tree structure.

The diameter can pass through any node, so track max sum of left and right subtree heights at each node.

Practice

1. What does the diameter of a binary tree represent?

easy

A. The length of the longest path between any two nodes in the tree

B. The number of nodes in the tree

C. The height of the tree

D. The number of leaf nodes

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, not just from root to leaf.

2. Step 2: Differentiate from height and node count

   Height is longest root-to-leaf path; node count is total nodes; diameter can be longer than height.

3. Final Answer:

   The length of the longest path between any two nodes in the tree -> Option A

4. Quick Check:

   Diameter = longest path length [OK]

Hint: Diameter is longest path between any two nodes, not just height [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter is always root to leaf

2. Which of the following Python function signatures is correct for computing the diameter of a binary tree node?

easy

A. def diameter(root: int) -> TreeNode:

B. def diameter(root: Optional[TreeNode]) -> int:

C. def diameter(root: TreeNode) -> str:

D. def diameter(root: List[int]) -> int:

Solution

1. Step 1: Identify correct parameter and return types

   Function takes a tree node or None and returns an integer diameter length.

2. Step 2: Check each option's signature

   def diameter(root: Optional[TreeNode]) -> int: matches expected input (node or None) and output (int). Others mismatch types.

3. Final Answer:

   def diameter(root: Optional[TreeNode]) -> int: -> Option B

4. Quick Check:

   Input node, output int diameter [OK]

Hint: Diameter function inputs root node, returns int length [OK]

Common Mistakes:

• Using wrong input type like int or list
• Returning wrong type like str or TreeNode
• Missing Optional for nullable root

3. What is the output of the following code snippet?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter(root):
    diameter_val = 0
    def depth(node):
        nonlocal diameter_val
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        diameter_val = max(diameter_val, left + right)
        return max(left, right) + 1
    depth(root)
    return diameter_val

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(diameter(root))

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Understand tree structure and depth calls

   Tree has root 1, left subtree with nodes 2,4,5 and right subtree with node 3. Longest path is 4->2->1->3 or 5->2->1->3 with length 3 edges.

2. Step 2: Calculate diameter_val during recursion

   At node 2, left and right depths are 1 each, sum 2; at root, left depth 2, right depth 1, sum 3 updates diameter_val to 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Diameter counts edges on longest path, not nodes [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring nonlocal update of diameter_val
• Misunderstanding tree structure

4. Find the error in the following diameter function and select the fix:

def diameter(root):
    diameter_val = 0
    def depth(node):
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        diameter_val = max(diameter_val, left + right)
        return max(left, right) + 1
    depth(root)
    return diameter_val

medium

A. Initialize diameter_val inside depth() function

B. Change 'diameter_val' to a global variable

C. Return diameter_val inside depth() function

D. Add 'nonlocal diameter_val' inside depth() to update outer variable

Solution

1. Step 1: Identify variable scope issue

   diameter_val is assigned inside depth() but not declared nonlocal, so assignment creates local variable, not updating outer diameter_val.

2. Step 2: Fix by declaring nonlocal

   Adding 'nonlocal diameter_val' inside depth() allows updating the outer variable correctly.

3. Final Answer:

   Add 'nonlocal diameter_val' inside depth() to update outer variable -> Option D

4. Quick Check:

   Use nonlocal to modify outer variable [OK]

Hint: Use nonlocal to update outer variable inside nested function [OK]

Common Mistakes:

• Forgetting nonlocal causes no diameter update
• Using global unnecessarily
• Returning diameter_val inside depth() breaks logic

5. Given a binary tree where some nodes have only one child, how does the diameter calculation handle paths through these nodes? Choose the correct statement about the diameter in such cases.

hard

A. Diameter counts the longest path even if it passes through nodes with only one child

B. Diameter ignores nodes with only one child when calculating longest path

C. Diameter is always the height of the tree when nodes have one child

D. Diameter equals the number of leaf nodes in the tree

Solution

1. Step 1: Understand diameter path definition

   Diameter is longest path between any two nodes, regardless of node children count.

2. Step 2: Consider nodes with one child

   Paths can pass through nodes with one child; these nodes do not exclude paths from consideration.

3. Final Answer:

   Diameter counts the longest path even if it passes through nodes with only one child -> Option A

4. Quick Check:

   Diameter includes all nodes on longest path [OK]

Hint: Diameter includes all nodes on longest path, child count doesn't exclude [OK]

Common Mistakes:

• Assuming nodes with one child are ignored
• Confusing diameter with height in skewed trees
• Thinking diameter equals leaf count