Diameter of Binary Tree in DSA Python - Execution Trace

Concept Flow - Diameter of Binary Tree

Start at root node

↓

Calculate left subtree height

↓

Calculate right subtree height

↓

Update max diameter if left height + right height is larger

↓

Return height of current node = max(left, right) + 1

↓

Repeat for left and right child nodes recursively

↓

End when leaf nodes reached (height=0)

We recursively find the height of left and right subtrees at each node, update the maximum diameter found so far as the sum of these heights, and return the height to parent nodes.

Execution Sample

DSA Python

def diameterOfBinaryTree(root):
    max_diameter = 0
    def height(node):
        nonlocal max_diameter
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        max_diameter = max(max_diameter, left + right)
        return max(left, right) + 1
    height(root)
    return max_diameter

This code calculates the diameter of a binary tree by recursively computing subtree heights and updating the maximum diameter.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Max Diameter	Return Height	Visual State
1	Visit root	1	?	?	0	?	Root(1)
2	Visit left child	2	?	?	0	?	Root(1) -> Left(2)
3	Visit left-left child	4	0	0	0	1	Root(1) -> Left(2) -> Left(4)
4	Return from left-left child	4	0	0	0	1	Leaf node 4 height=1
5	Visit left-right child	5	0	0	0	1	Root(1) -> Left(2) -> Right(5)
6	Return from left-right child	5	0	0	0	1	Leaf node 5 height=1
7	Calculate left subtree height at node 2	2	1	1	2	2	Node 2 height=2, max diameter=2
8	Visit right child	3	?	?	2	?	Root(1) -> Right(3)
9	Visit right-left child	6	0	0	2	1	Root(1) -> Right(3) -> Left(6)
10	Return from right-left child	6	0	0	2	1	Leaf node 6 height=1
11	Visit right-right child	7	0	0	2	1	Root(1) -> Right(3) -> Right(7)
12	Return from right-right child	7	0	0	2	1	Leaf node 7 height=1
13	Calculate right subtree height at node 3	3	1	1	2	2	Node 3 height=2, max diameter=2
14	Calculate diameter at root	1	2	2	4	3	Root node height=3, max diameter=4
15	Return final diameter	1	2	2	4	3	Diameter of tree is 4

💡 All nodes visited, recursion unwound, max diameter found as 4

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	After Step 12	After Step 13	After Step 14	Final
max_diameter	0	0	0	2	2	2	4	4
left	?	1	1	1	1	1	2	2
right	?	?	1	1	1	1	2	2
Return Height	?	1	1	2	1	2	3	3

Key Moments - 3 Insights

Why do we add left and right heights to update max diameter?

Because the diameter is the longest path between two nodes, which passes through the current node as left height + right height (see Step 7 and Step 14 in execution_table).

Why do we return max(left, right) + 1 as height?

Height is the longest path from current node down to a leaf, so we take the larger subtree height and add 1 for the current node (see Return Height column in execution_table).

What happens when a node is None (leaf's child)?

We return 0 height, which stops recursion and helps calculate heights correctly (see Step 3 and Step 5 where left and right heights are 0).

Visual Quiz - 3 Questions

Look at the execution_table at Step 14, what is the max diameter value?

A 2

B 4

C 3

D 0

💡 Hint

Check the Max Diameter column at Step 14 in execution_table

At which step does the left subtree height of node 2 become 1?

A Step 3

B Step 7

C Step 6

D Step 12

💡 Hint

Look at Left Height column for node 2 in execution_table

If the tree had no right subtree, how would max diameter change at root?

A It would be equal to left height

B It would be zero

C It would be sum of left and right heights (which is left height only)

D It would be one

💡 Hint

Diameter is left height + right height; if right height is zero, diameter equals left height (see concept_flow)

Concept Snapshot

Diameter of Binary Tree:
- Diameter = longest path between any two nodes
- At each node, diameter = left height + right height
- Use recursion to get heights of subtrees
- Update max diameter during recursion
- Return height = max(left, right) + 1
- Final max diameter is answer

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. We find it by recursively calculating the height of left and right subtrees for each node. At each node, we update the maximum diameter as the sum of left and right subtree heights. The height returned to parent nodes is the maximum of left and right heights plus one for the current node. When a node is None, we return zero height. This process continues until all nodes are visited, and the maximum diameter found is returned as the result.

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