LeetCode Solutions Blog

Cousins in Binary Tree II

Number: 2677

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree, replace the value of each node with the sum of values of all its cousins. Two nodes are considered cousins if they are on the same level but have different parents. The root node (or any node without cousins) should have its value replaced with 0.

Key Insights

Use level-order traversal to process nodes level by level.
For each level, calculate the total sum of node values.
Group nodes by their parent, and for each node compute its new value as (total level sum - sum of values of nodes with the same parent).
For the root node (or nodes with no parent), if there are no cousins, assign 0.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes, since we visit every node exactly once. Space Complexity: O(N), to store nodes in the queue during BFS and group sums for each level.

Solution

We employ a breadth-first search (BFS) to traverse the tree level by level. For every level, first compute the total sum of node values. Then, by using a hash table (or dictionary) to group nodes by their parent, compute the sum of sibling nodes (nodes coming from the same parent). For each node, subtract its parent's group sum from the total level sum to get the cousin sum, and update the node’s value. The root node and any node with no cousins are updated to 0. This approach ensures each node is processed exactly once, keeping the overall time complexity linear.

Code Solutions

# 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: TreeNode) -> TreeNode:
        if not root:
            return None
        
        from collections import deque
        # Initialize queue with tuple (node, parent)
        queue = deque([(root, None)])
        
        # Process level by level
        while queue:
            level_size = len(queue)
            # total sum for the current level
            level_sum = 0
            # Dictionary to map parent's id to sum of child values
            parent_to_sum = {}
            
            # First pass: calculate level_sum and accumulate sum for each family (grouped by parent)
            level_nodes = []
            for _ in range(level_size):
                node, parent = queue.popleft()
                level_sum += node.val
                level_nodes.append((node, parent))
                # Use parent's id to denote a group (None remains None)
                if parent not in parent_to_sum:
                    parent_to_sum[parent] = 0
                parent_to_sum[parent] += node.val
            
            # Second pass: update each node's value
            for node, parent in level_nodes:
                # If parent's children sum is available, subtract it from total level sum.
                # For root, parent is None, so its cousin sum is 0.
                node.val = level_sum - parent_to_sum[parent]
                
                # Add children to the queue for the next level with current node as parent.
                if node.left:
                    queue.append((node.left, node))
                if node.right:
                    queue.append((node.right, node))
                    
        # Set root's value to 0 since it has no cousins.
        root.val = 0
        return root