How do you solve Cousins in Binary Tree II on LeetCode?

Cousins in Binary Tree II (LeetCode #2641) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Cousins are nodes at the same depth with different parents, which requires careful tracking of depth and parent relationships.

What is the brute force solution for Cousins in Binary Tree II?

The brute force approach for Cousins in Binary Tree II is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we traverse the tree for each node to find its cousins and calculate their sum. This is straightforward but inefficient as we repeatedly traverse parts of the tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Cousins in Binary Tree II?

Cousins in Binary Tree II uses the following concepts: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search (DFS), Hash Map for storing sums and counts.

What are the interview tips for Cousins in Binary Tree II?

Clearly explain your thought process and approach before jumping into coding. Consider edge cases and discuss how your solution handles them. Practice writing clean and efficient code, as readability is important in interviews.

What are common mistakes when solving Cousins in Binary Tree II?

Not properly distinguishing between nodes at the same depth and ensuring they have different parents. Failing to handle edge cases, such as trees with only one node or all nodes having the same depth.

#2641

Cousins in Binary Tree II

Medium

Hash TableTreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First Search (DFS)Hash Map for storing sums and counts

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal solution, we use a two-pass DFS approach. The first pass calculates the sum of values at each depth, and the second pass updates each node's value with the sum of its cousins.

⚙️

Algorithm

2 steps

1Step 1: Perform a DFS to calculate the sum of values for each depth and count the number of nodes at each depth.
2Step 2: Perform another DFS to replace each node's value with the sum of its cousins, which is the total sum at that depth minus the node's own value.

solution.py33 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def replaceCousins(root):
9    if not root:
10        return root
11
12    depth_sum = {}
13    depth_count = {}
14
15    def dfs(node, depth):
16        if not node:
17            return
18        depth_sum[depth] = depth_sum.get(depth, 0) + node.val
19        depth_count[depth] = depth_count.get(depth, 0) + 1
20        dfs(node.left, depth + 1)
21        dfs(node.right, depth + 1)
22
23    dfs(root, 0)
24
25    def update(node, depth):
26        if not node:
27            return
28        node.val = depth_sum[depth] - node.val
29        update(node.left, depth + 1)
30        update(node.right, depth + 1)
31
32    update(root, 0)
33    return root

ℹ

Complexity note: This complexity arises because we traverse the tree twice, once for calculating sums and once for updating values, leading to O(n) + O(n) = O(n).

1Cousins are nodes at the same depth with different parents, which requires careful tracking of depth and parent relationships.
2Using a two-pass DFS allows us to efficiently calculate and update values without redundant traversals.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.