We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cousins in Binary Tree II

Difficulty: Medium

Problem Description

Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins' values. Two nodes of a binary tree are cousins if they have the same depth with different parents. Return the root of the modified tree.

Key Insights

  • Nodes are considered cousins if they are at the same depth and have different parents.
  • To solve the problem, we need to traverse the tree and calculate the sum of cousins for each node.
  • A breadth-first search (BFS) or depth-first search (DFS) can be used to explore the tree level by level or recursively.
  • We can keep track of the sum of values at each depth and the number of nodes at each depth to compute the cousins' sums effectively.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we need to visit each node once.

Space Complexity: O(N), for storing the node values at each depth, or O(H) for the recursion stack in the case of DFS, where H is the height of the tree.

Solution

To solve the problem, we will use a breadth-first search (BFS) approach. During the BFS traversal, we will maintain a list to store the values of nodes at each depth. For each node, we will compute the sum of its cousins' values by subtracting its own value from the total sum of values at its depth. Finally, we will replace each node's value with the computed sum.

Code Solutions

from collections import defaultdict, deque

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

def replaceCousins(root: TreeNode) -> TreeNode:
    if not root:
        return root

    # Dictionary to hold sum of values at each depth
    depth_sum = defaultdict(int)
    # Dictionary to hold count of nodes at each depth
    depth_count = defaultdict(int)
    
    # BFS to calculate sums and counts
    queue = deque([(root, 0)])  # (node, depth)
    while queue:
        node, depth = queue.popleft()
        depth_sum[depth] += node.val
        depth_count[depth] += 1
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

    # DFS to replace values with the sum of cousins
    def dfs(node, depth):
        if not node:
            return
        # Calculate the sum of cousins
        cousin_sum = depth_sum[depth] - node.val
        node.val = cousin_sum
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return root
← Back to All Questions