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. Given the following code snippet for building a binary tree from preorder and inorder traversals, what is the value of inorder_index after processing the second element of preorder = [3,9,20] and inorder = [9,3,20]?

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Initialize variables

   Start with root=3, stack=[3], inorder_index=0 (inorder[0]=9).

2. Step 2: Process second preorder element (9)

   Top of stack is 3, which is not equal to inorder[0]=9, so 9 becomes left child of 3 and is pushed to stack. inorder_index remains 0.

3. Step 3: Process third preorder element (20)

   Top of stack is 9, which equals inorder[0]=9, so pop 9 and increment inorder_index to 1. Now top is 3, equals inorder[1]=3, pop 3 and increment inorder_index to 2. Then 20 becomes right child of 3 and is pushed to stack.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   inorder_index increments twice after processing 20, so after second element it is 1 [OK]

Hint: inorder_index increments only when stack top matches inorder element [OK]

Common Mistakes:

• Off-by-one increment of inorder_index
• Confusing preorder and inorder indices
• Forgetting to pop stack before incrementing inorder_index

2. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

easy

A. True

B. False

C. Raises an exception due to null pointer

D. Returns True only if the root value equals targetSum

Solution

1. Step 1: Trace the path sums

   Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.

2. Step 2: Confirm code logic

   The DFS returns True as soon as it finds the matching path sum at a leaf node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Path 5↔4↔11↔2 sums to 22, so return True [OK]

Hint: Check all root-to-leaf paths, not just partial sums [OK]

Common Mistakes:

• Stopping at non-leaf nodes
• Ignoring leaf node condition

3. What is the time complexity of the parent pointer + ancestor set approach for finding the Lowest Common Ancestor in a binary tree with n nodes and height h?

medium

A. O(h^2) because ancestor set lookups take O(h) each and we do up to h lookups

B. O(n^2) because each node's parent is checked multiple times

C. O(n) to build parent map plus O(h) to find LCA, total O(n)

D. O(n log n) due to sorting ancestors before comparison

Solution

1. Step 1: Identify parent map construction cost

   Building the parent map requires visiting each node once, O(n).

2. Step 2: Analyze ancestor set and LCA search

   Ancestor set insertion and lookup are O(1) average. Traversing up to height h for p and q is O(h). Total is O(n) + O(h) ≈ O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Parent map O(n) + ancestor lookup O(h) = O(n) total [OK]

Hint: Parent map build dominates; ancestor lookup is O(h) [OK]

Common Mistakes:

• Confusing ancestor set lookup as O(h)
• Assuming sorting ancestors needed
• Overestimating repeated parent checks

4. What is the time complexity of the iterative DFS solution for finding all root-to-leaf paths with a given sum in a binary tree with N nodes and maximum path length L?

medium

A. O(N) because each node is visited once

B. O(N^2) because all pairs of nodes are compared during traversal

C. O(N * L) because each node's path is copied when pushed onto the stack

D. O(L) because only the path length affects complexity

Solution

1. Step 1: Identify operations per node

   Each node is visited once, but path copying of length up to L occurs when pushing onto stack.

2. Step 2: Calculate total complexity

   Copying paths of length L for up to N nodes leads to O(N * L) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Path copying dominates, so complexity is O(N * L) [OK]

Hint: Path copying causes O(N * L), not just O(N) [OK]

Common Mistakes:

• Assuming O(N) ignoring path copying
• Confusing with quadratic complexity from unrelated operations

5. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity