LeetCode 2641 - Cousins in Binary Tree II
The problem gives us the root of a binary tree and asks us to replace every node’s value with the sum of all of its cousins’ values.
Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Solution
Problem Understanding
The problem gives us the root of a binary tree and asks us to replace every node’s value with the sum of all of its cousins’ values.
Two nodes are considered cousins if:
- They are at the same depth in the tree
- They do not share the same parent
The depth of the root is 0, its children are at depth 1, grandchildren at depth 2, and so on.
For every node, we need to compute:
sum of all nodes at the same depth
minus
sum of nodes that share the same parent
The result should overwrite the original node values directly in the tree, and we must return the modified root.
For example, suppose a level contains nodes:
[1, 10, 7]
If 1 and 10 are siblings and 7 belongs to another parent:
- Node
1should become7 - Node
10should become7 - Node
7should become1 + 10 = 11
The constraints are important:
- Up to
10^5nodes - Node values up to
10^4
A quadratic solution is impossible because traversing the tree repeatedly for every node would be far too slow. We need an algorithm that processes the tree in linear time.
Several edge cases are important:
- A tree with only one node
- A completely skewed tree
- Nodes with only one child
- Levels containing only siblings and no cousins
- Large trees where recursion depth might matter in some languages
The problem guarantees the input is a valid binary tree and contains at least one node.
Approaches
Brute Force Approach
A straightforward solution would be:
- For every node, determine its depth and parent.
- Traverse the entire tree again to find every node at the same depth.
- Sum the values of nodes whose parent is different.
- Replace the node’s value with that sum.
This works because it directly follows the definition of cousins.
However, this approach is extremely inefficient. If we perform a traversal for every node, the total complexity becomes approximately O(n^2) in the worst case.
With 10^5 nodes, this is far too slow.
Key Insight
The crucial observation is that cousin relationships depend only on nodes within the same level.
For a node:
cousin sum =
(total sum of current level)
-
(sum of sibling group)
Instead of computing cousin sums individually, we can process the tree level by level.
At each depth:
- Compute the total sum of all child nodes in the next level.
- For every parent, compute the sum of its own children.
- Assign each child:
next_level_sum - sibling_sum
This avoids repeated traversals and allows the entire tree to be processed in linear time.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly scans levels for every node |
| Optimal | O(n) | O(n) | Level-order traversal with level sums |
Algorithm Walkthrough
Optimal BFS Algorithm
- Start with a breadth-first traversal using a queue.
Breadth-first traversal is ideal because cousin relationships are defined by depth. BFS naturally processes nodes level by level.
2. Set the root value to 0.
The root has no cousins because there are no other nodes at depth 0.
3. For every level, compute the total value of all children in the next level.
As we process the current level, we inspect each node’s left and right children and accumulate their values into next_level_sum.
4. For each parent node, compute the sum of its own children.
This sibling-group sum is:
child_sum = left_child_value + right_child_value
- Replace each child’s value.
Each child should become:
next_level_sum - child_sum
This removes the values of siblings while keeping all cousin values. 6. Add children to the queue.
After updating values, push the children into the queue so the next BFS iteration processes the next depth level. 7. Continue until the queue becomes empty.
Why it works
At every depth level, all cousin nodes are exactly the nodes in that level excluding siblings.
The algorithm computes:
all nodes at level
minus
nodes with same parent
Since every node belongs to exactly one sibling group, subtracting the sibling-group sum leaves only cousin values. BFS guarantees we process nodes grouped correctly by depth, so every replacement is computed using the original level structure.
Python Solution
from collections import deque
from typing import Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = deque([root])
root.val = 0
while queue:
level_size = len(queue)
next_level_sum = 0
# First pass, compute total sum of next level
current_level_nodes = []
for _ in range(level_size):
node = queue.popleft()
current_level_nodes.append(node)
if node.left:
next_level_sum += node.left.val
if node.right:
next_level_sum += node.right.val
# Second pass, update child values
for node in current_level_nodes:
sibling_sum = 0
if node.left:
sibling_sum += node.left.val
if node.right:
sibling_sum += node.right.val
cousin_sum = next_level_sum - sibling_sum
if node.left:
node.left.val = cousin_sum
queue.append(node.left)
if node.right:
node.right.val = cousin_sum
queue.append(node.right)
return root
The implementation uses a standard BFS queue with collections.deque.
The root value is immediately set to 0 because it has no cousins.
For each level, the algorithm first computes the total sum of all nodes in the next level. This is done before modifying any child values, ensuring we still use the original values.
The nodes of the current level are temporarily stored in current_level_nodes. This allows us to perform a second pass where we calculate each sibling-group sum and update child values correctly.
The cousin sum for every child is:
next_level_sum - sibling_sum
After updating a child’s value, the child is added to the queue for future processing.
Because every node is visited once, the solution runs in linear time.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func replaceValueInTree(root *TreeNode) *TreeNode {
queue := []*TreeNode{root}
root.Val = 0
for len(queue) > 0 {
levelSize := len(queue)
nextLevelSum := 0
currentLevel := make([]*TreeNode, 0, levelSize)
// First pass, compute next level sum
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
currentLevel = append(currentLevel, node)
if node.Left != nil {
nextLevelSum += node.Left.Val
}
if node.Right != nil {
nextLevelSum += node.Right.Val
}
}
// Second pass, update children
for _, node := range currentLevel {
siblingSum := 0
if node.Left != nil {
siblingSum += node.Left.Val
}
if node.Right != nil {
siblingSum += node.Right.Val
}
cousinSum := nextLevelSum - siblingSum
if node.Left != nil {
node.Left.Val = cousinSum
queue = append(queue, node.Left)
}
if node.Right != nil {
node.Right.Val = cousinSum
queue = append(queue, node.Right)
}
}
}
return root
}
The Go implementation follows the same BFS strategy as the Python version.
The queue is implemented using a slice of *TreeNode.
Go uses nil checks instead of Python truthiness checks.
Integer overflow is not a concern because the maximum possible level sum remains safely within Go’s int range under the given constraints.
Worked Examples
Example 1
Input:
[5,4,9,1,10,null,7]
Tree:
5
/ \
4 9
/ \ \
1 10 7
Initial State
| Level | Nodes |
|---|---|
| 0 | [5] |
Set root value to 0.
Tree becomes:
0
/ \
4 9
/ \ \
1 10 7
Processing Level 0
Children are [4, 9]
next_level_sum = 4 + 9 = 13
Sibling sum for root:
4 + 9 = 13
Each child becomes:
13 - 13 = 0
Tree:
0
/ \
0 0
/ \ \
1 10 7
Processing Level 1
Children are [1, 10, 7]
next_level_sum = 1 + 10 + 7 = 18
For parent 0 on left:
sibling_sum = 1 + 10 = 11
cousin_sum = 18 - 11 = 7
So:
1 -> 7
10 -> 7
For parent 0 on right:
sibling_sum = 7
cousin_sum = 18 - 7 = 11
So:
7 -> 11
Final tree:
0
/ \
0 0
/ \ \
7 7 11
Output:
[0,0,0,7,7,null,11]
Example 2
Input:
[3,1,2]
Tree:
3
/ \
1 2
Processing Root
Children sum:
1 + 2 = 3
Sibling sum:
1 + 2 = 3
Each child becomes:
3 - 3 = 0
Final tree:
0
/ \
0 0
Output:
[0,0,0]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is visited exactly once |
| Space | O(n) | Queue may store an entire level of the tree |
The BFS traversal processes each node one time. All operations inside the traversal are constant time, so the total runtime is linear in the number of nodes.
The queue can contain up to one full tree level at once. In the worst case of a complete binary tree, this can be approximately n / 2, resulting in O(n) auxiliary space.
Test Cases
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(values):
if not values:
return None
root = TreeNode(values[0])
queue = deque([root])
index = 1
while queue and index < len(values):
node = queue.popleft()
if index < len(values) and values[index] is not None:
node.left = TreeNode(values[index])
queue.append(node.left)
index += 1
if index < len(values) and values[index] is not None:
node.right = TreeNode(values[index])
queue.append(node.right)
index += 1
return root
def tree_to_list(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
# Example 1
root = build_tree([5,4,9,1,10,None,7])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0,0,0,7,7,None,11] # standard example
# Example 2
root = build_tree([3,1,2])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0,0,0] # no cousins exist
# Single node
root = build_tree([1])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0] # root has no cousins
# Left-skewed tree
root = build_tree([1,2,None,3,None,4])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0,0,None,0,None,0] # every level has one node
# Complete binary tree
root = build_tree([1,2,3,4,5,6,7])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0,0,0,13,13,9,9] # cousin sums across full levels
# Nodes with one child
root = build_tree([1,2,3,4,None,None,5])
result = Solution().replaceValueInTree(root)
assert tree_to_list(result) == [0,0,0,5,None,None,4] # asymmetric structure
Test Summary
| Test | Why |
|---|---|
[5,4,9,1,10,null,7] |
Validates the main example |
[3,1,2] |
Confirms no cousins case |
[1] |
Tests smallest possible tree |
| Left-skewed tree | Ensures sparse depth handling |
| Complete binary tree | Verifies multiple cousin groups |
| Asymmetric tree | Tests missing children logic |
Edge Cases
Single Node Tree
A tree containing only the root is an important edge case because the root has no cousins. A buggy implementation might accidentally preserve the original value instead of replacing it with 0.
This implementation handles the case correctly by explicitly setting:
root.val = 0
before beginning BFS processing.
Skewed Trees
A completely left-skewed or right-skewed tree behaves almost like a linked list. Every level contains exactly one node, meaning no cousins ever exist.
Some implementations incorrectly assume sibling groups always contain two children. This solution safely checks for missing children and computes sums only from existing nodes.
Parents With One Child
Some nodes may have only a left child or only a right child.
For example:
1
/
2
The sibling-group sum must include only existing children. The implementation carefully computes:
if node.left:
sibling_sum += node.left.val
and similarly for the right child.
This ensures missing children do not incorrectly contribute to sums.