Diameter of Binary Tree

▶

Steps

setup

Initialize diameter and start recursion at root

The diameter variable is initialized to 0. The recursive height function is called starting at the root node (value 1).

💡 Initializing diameter to zero sets the baseline for updates. Starting at the root begins the bottom-up height calculations.

Line:

diameter = 0
height(root)

💡 The algorithm will explore all nodes recursively to compute heights and update diameter.

traverse

Recurse to left child of root (node 2)

The height function is called recursively on the left child of node 1, which is node 2.

💡 The algorithm explores the left subtree first to compute its height before combining with the right subtree.

Line:

left_height = height(node.left)  # node 2

💡 Height of node 2 must be computed before node 1's height can be finalized.

traverse

Recurse to left child of node 2 (node 4)

The height function is called recursively on the left child of node 2, which is node 4 (a leaf).

💡 Leaf nodes have height 1, so this base case will start returning values up the recursion.

Line:

left_height = height(node.left)  # node 4

💡 Reaching a leaf node allows the recursion to start returning heights.

fill_cells

Return height 0 for null children of node 4

Since node 4 has no children, recursive calls on its left and right return 0 height.

💡 Null children represent empty subtrees with height 0, the base case for recursion.

Line:

if not node:
    return 0

💡 Base case returns 0 height for missing children.

fill_cells

Compute height of node 4 and update diameter

Height of node 4 is 1 + max(0,0) = 1. Diameter remains 0 since left_height + right_height = 0.

💡 Leaf node height is 1; diameter update checks if path through node 4 is longer than current max.

Line:

diameter = max(diameter, left_height + right_height)
return 1 + max(left_height, right_height)

💡 Height calculation and diameter update at leaf nodes set the foundation for parent computations.

traverse

Recurse to right child of node 2 (node 5)

The height function is called recursively on the right child of node 2, which is node 5 (a leaf).

💡 The algorithm now explores the right subtree of node 2 to compute its height.

Line:

right_height = height(node.right)  # node 5

💡 Both children of node 2 must be processed to compute node 2's height and update diameter.

fill_cells

Return height 0 for null children of node 5

Node 5 has no children, so recursive calls return 0 height for both left and right.

💡 Base case for leaf node children returns 0 height.

Line:

if not node:
    return 0

💡 Base case ensures leaf nodes have height 1.

fill_cells

Compute height of node 5 and update diameter

Height of node 5 is 1 + max(0,0) = 1. Diameter remains 0 since left_height + right_height = 0.

💡 Leaf node height is 1; diameter update checks if path through node 5 is longer than current max.

Line:

diameter = max(diameter, left_height + right_height)
return 1 + max(left_height, right_height)

💡 Height and diameter at node 5 are computed similarly to node 4.

fill_cells

Compute height of node 2 and update diameter

Height of node 2 is 1 + max(1,1) = 2. Diameter is updated to max(0, 1+1) = 2.

💡 Node 2's height depends on its children's heights; diameter updates if path through node 2 is longer.

Line:

diameter = max(diameter, left_height + right_height)
return 1 + max(left_height, right_height)

💡 Diameter now reflects the longest path through node 2 connecting nodes 4 and 5.

traverse

Recurse to right child of root (node 3)

The height function is called recursively on the right child of root node 1, which is node 3 (a leaf).

💡 The algorithm now explores the right subtree of the root to compute its height.

Line:

right_height = height(node.right)  # node 3

💡 Both subtrees of root must be processed to compute root's height and update diameter.

fill_cells

Return height 0 for null children of node 3

Node 3 has no children, so recursive calls return 0 height for both left and right.

💡 Base case for leaf node children returns 0 height.

Line:

if not node:
    return 0

💡 Base case ensures leaf nodes have height 1.

fill_cells

Compute height of node 3 and update diameter

Height of node 3 is 1 + max(0,0) = 1. Diameter remains 2 since left_height + right_height = 0.

💡 Leaf node height is 1; diameter update checks if path through node 3 is longer than current max.

Line:

diameter = max(diameter, left_height + right_height)
return 1 + max(left_height, right_height)

💡 Height and diameter at node 3 are computed similarly to other leaves.

fill_cells

Compute height of root node 1 and update diameter

Height of node 1 is 1 + max(2,1) = 3. Diameter is updated to max(2, 2+1) = 3.

💡 Root height depends on left and right subtree heights; diameter updates if path through root is longest.

Line:

diameter = max(diameter, left_height + right_height)
return 1 + max(left_height, right_height)

💡 Diameter now reflects the longest path through the root connecting nodes 4 or 5 to node 3.

reconstruct

Return final diameter

The recursion completes and the final diameter value 3 is returned as the longest path length in edges.

💡 Returning the diameter after full traversal gives the longest path in the tree.

Line:

return diameter

💡 The diameter variable holds the maximum path length found during recursion.

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

def diameterOfBinaryTree(root):
    diameter = 0  # STEP 1: initialize diameter
    def height(node):
        nonlocal diameter
        if not node:  # STEP 4 & 7 & 11: base case for null nodes
            return 0
        left_height = height(node.left)  # STEP 2,3,6,10: recurse left
        right_height = height(node.right)  # STEP 6,10: recurse right
        diameter = max(diameter, left_height + right_height)  # STEP 5,8,9,12,13: update diameter
        return 1 + max(left_height, right_height)  # STEP 5,8,9,12,13: return height
    height(root)  # STEP 1: start recursion
    return diameter  # STEP 14: return final diameter

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(diameterOfBinaryTree(root))  # Output: 3

📊

Diameter of Binary Tree - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node's height calculation and diameter update reveals how the longest path is found without redundant computations.

Item 0 - wt:0 val:1

i\w	0	1
i=0	?	?

root node start

Item 1 - wt:0 val:2

i\w	0	1
i=0	?	?
i=1	?	?

left child of root

Item 2 - wt:0 val:4

i\w	0	1
i=0	?	?
i=1	?	?
i=2	?	?

left child of node 2

Item 2 - wt:0 val:4

i\w	0	1
i=0	?	?
i=1	?	?
i=2	0	0

null child height 0

Item 2 - wt:0 val:4

i\w	0	1
i=0	?	?
i=1	?	?
i=2	1	0

height=1

Item 3 - wt:0 val:5

i\w	0	1
i=0	?	?
i=1	?	?
i=2	1	0
i=3	?	?

right child of node 2

Item 3 - wt:0 val:5

i\w	0	1
i=0	?	?
i=1	?	?
i=2	1	0
i=3	0	0

null child height 0

Item 3 - wt:0 val:5

i\w	0	1
i=0	?	?
i=1	?	?
i=2	1	0
i=3	1	0

height=1

Item 1 - wt:0 val:2

i\w	0	1
i=0	?	?
i=1	2	2
i=2	1	0
i=3	1	0

height=2

Item 4 - wt:0 val:3

i\w	0	1
i=0	?	?
i=1	2	2
i=2	1	0
i=3	1	0
i=4	?	?

right child of root

Item 4 - wt:0 val:3

i\w	0	1
i=0	?	?
i=1	2	2
i=2	1	0
i=3	1	0
i=4	0	0

null child height 0

Item 4 - wt:0 val:3

i\w	0	1
i=0	?	?
i=1	2	2
i=2	1	0
i=3	1	0
i=4	1	0

height=1

Item 0 - wt:0 val:1

i\w	0	1
i=0	3	3
i=1	2	2
i=2	1	0
i=3	1	0
i=4	1	0

height=3

Item 0 - wt:0 val:1

i\w	0	1
i=0	3	3
i=1	2	2
i=2	1	0
i=3	1	0
i=4	1	0

final heights and diameter

Key Takeaways

✓ The diameter is computed by combining left and right subtree heights at each node during a single bottom-up traversal.

This insight is hard to see from code alone because the diameter update is embedded inside recursion, but the visualization shows how subtree heights combine.

✓ Height values propagate from leaves up to the root, enabling diameter updates at every node based on subtree heights.

Seeing the monotonic growth of heights clarifies why the recursion returns correct values for diameter calculation.

✓ The longest path (diameter) may pass through the root or any other node, and the algorithm tracks the maximum sum of left and right heights globally.

The visualization shows diameter updates at multiple nodes, illustrating how the maximum path is found anywhere in the tree.

Practice

1. You are given a binary tree where each node contains an integer value (which can be negative). You need to find the maximum sum of values along any path in the tree, where a path can start and end at any node and must be connected through parent-child links. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Depth-first search with dynamic programming on trees, tracking maximum gains from subtrees and updating a global maximum path sum

B. Divide and conquer by splitting the tree into subtrees and combining their maximum sums without considering paths crossing the root

C. Breadth-first search to find the longest path and sum node values along it

D. Greedy traversal selecting the maximum child at each node without backtracking

Solution

1. Step 1: Understand the problem constraints

   The path can start and end at any node, and may include both left and right children of a node, so a simple greedy or BFS approach won't capture all possibilities.

2. Step 2: Identify the correct algorithmic pattern

   Dynamic programming on trees with DFS allows computing maximum gains from left and right subtrees and updating a global maximum path sum that includes paths passing through the current node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP on trees with global tracking handles negative values and arbitrary path start/end [OK]

Hint: DP on trees tracks max gains and global max path sum [OK]

Common Mistakes:

• Greedy misses paths crossing nodes
• BFS doesn't handle arbitrary start/end
• Divide and conquer misses cross-root paths

2. Consider the following code snippet implementing the topological sort based DP for longest increasing path. Given the input matrix = [[9,9,4],[6,6,8],[2,1,1]], what is the final returned value?

easy

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Trace dp updates for smallest cell (1,2) with value 1

   Initialize dp with 1s. Process cells in ascending order: start from value 1 cells, update neighbors with larger values increasing dp accordingly.

2. Step 2: Identify longest path length after processing all cells

   Longest increasing path is 4, e.g., 1 -> 2 -> 6 -> 9.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest path length matches known example output [OK]

Hint: Trace dp updates in ascending order [OK]

Common Mistakes:

• Off-by-one in dp updates
• Confusing max path length with number of edges
• Ignoring boundary checks

3. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with nested loops checking all pairs of envelopes for nesting conditions

B. Greedy algorithm that sorts envelopes by width and picks the tallest envelope at each step

C. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search

D. Use a graph and find the longest path by topological sorting

Solution

1. Step 1: Understand problem constraints

   The problem requires strict nesting by both width and height, so sorting by width ascending and height descending ensures envelopes with the same width do not interfere with LIS on height.

2. Step 2: Recognize LIS pattern on heights

   After sorting, the problem reduces to finding the LIS on heights, which can be done optimally with binary search for O(n log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by width ascending and height descending + LIS on heights -> optimal solution [OK]

Hint: Sort width asc, height desc, then LIS on height [OK]

Common Mistakes:

• Sorting both width and height ascending causes incorrect LIS
• Using greedy height selection without sorting
• Applying graph longest path without sorting

4. The following code attempts to count arithmetic subsequences but contains a subtle bug. Identify the line causing incorrect counting of subsequences.

medium

A. dp = [defaultdict(int) for _ in range(n)]

B. count_at_j = dp[j][diff]

C. dp[i][diff] += count_at_j + 1

D. total += dp[i][diff] # adding wrong value to total

Solution

1. Step 1: Understand counting logic

   Total should only increase by count_at_j, which counts subsequences extended by nums[i]. Adding dp[i][diff] counts pairs and subsequences multiple times.

2. Step 2: Identify incorrect line

   Line adding dp[i][diff] to total causes double counting; it should add only count_at_j.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct counting adds count_at_j, not dp[i][diff] [OK]

Hint: Only add count_at_j to total, not dp[i][diff] [OK]

Common Mistakes:

• Adding dp[i][diff] to total
• Not initializing dp correctly
• Counting pairs as subsequences

5. The following code attempts to count the number of longest increasing subsequences using DP arrays. Identify the bug that causes incorrect counting of LIS.

medium

A. counts array is initialized with zeros instead of ones

B. lengths array should be initialized with zeros instead of ones

C. The condition nums[j] < nums[i] should be nums[j] <= nums[i]

D. The final sum should be over counts where lengths are less than max_len

Solution

1. Step 1: Check initialization of counts array

   Counts represent number of LIS ending at each index; initially each element alone forms LIS of length 1, so counts[i] must start at 1, not 0.

2. Step 2: Consequence of zero initialization

   With counts initialized to 0, counts[i] remains 0 unless updated, causing undercounting of LIS and incorrect final result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialize counts with 1 to count single-element subsequences [OK]

Hint: Counts must start at 1 to count single elements [OK]

Common Mistakes:

• Initializing counts with zeros
• Using <= instead of <
• Summing counts incorrectly