Cousins in Binary Tree II

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. Note that the depth of a node is the number of edges in the path from the root node to it.

For example: Input: root = [5,4,9,1,10,null,7] Output: [0,0,0,7,7,null,11]

Explanation:

• Node with value 5 does not have any cousins so its sum is 0.
• Node with value 4 does not have any cousins so its sum is 0.
• Node with value 9 does not have any cousins so its sum is 0.
• Node with value 1 has a cousin with value 7 so its sum is 7.
• Node with value 10 has a cousin with value 7 so its sum is 7.
• Node with value 7 has cousins with values 1 and 10 so its sum is 11.

Constraints: The number of nodes in the tree is in the range [1, 10^5]. 1 <= Node.val <= 10^4

# 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]:
        if not root:
            return root

        root.val = 0  # Root has no cousins, so sum is 0
        queue = [root]

        while queue:
            next_level = []
            level_sum = 0
            children_values = {}
            
            #First we calculate the level sum and the children's values to be used later
            for node in queue:
                if node.left:
                    level_sum += node.left.val
                    next_level.append(node.left)
                if node.right:
                    level_sum += node.right.val
                    next_level.append(node.right)
            
            #Second, we modify the children's values based on the level sum
            for node in queue:
                cousin_sum = level_sum
                if node.left:
                    cousin_sum -= node.left.val
                if node.right:
                    cousin_sum -= node.right.val

                if node.left:
                    node.left.val = cousin_sum
                if node.right:
                    node.right.val = cousin_sum

            queue = next_level

        return root

Explanation:

1. Initialization:

   • If the root is None, return it.
   • Set the root's value to 0 because it has no cousins.
   • Initialize a queue with the root node for level-order traversal.

2. Level-Order Traversal:

   • The while queue loop continues as long as there are nodes to process.
   • next_level list stores the nodes for the next level.
   • level_sum calculates the sum of all node values at the current level.

3. Calculating Level Sum:

   • Iterate through the current level's nodes in the queue.
   • If a node has a left or right child, add its value to level_sum and append the child to next_level.

4. Updating Node Values:

   • Iterate through the nodes in the current level again.
   • Calculate cousin_sum by subtracting the left and right child values (if they exist) from level_sum.
   • Update the left and right child values with cousin_sum.

5. Moving to the Next Level:

   • Set queue to next_level to process the next level of the tree.

6. Return Root:

   • After processing all levels, return the modified root.

Example:

Consider the input root = [5,4,9,1,10,null,7]

• Initially, root.val is set to 0.
• Level 1: Nodes 4 and 9. The sum is 4 + 9 = 13. So the cousins sum for both will be 0 since they dont have siblings on the root level
• Level 2: Nodes 1, 10, and 7. The level sum is 1 + 10 + 7 = 18.
  • Node 1 has a cousin 7. cousin_sum = 18 - 1 - 10 = 7. New value of node 1 is 7.
  • Node 10 has a cousin 7. cousin_sum = 18 - 10 - 1 = 7. New value of node 10 is 7.
  • Node 7 has cousins 1 and 10. cousin_sum = 18 - 7 = 11. New value of node 7 is 11.

Time and Space Complexity:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. This is due to the queue used for level-order traversal. In the worst case (a complete binary tree), W can be approximately N/2, so the space complexity can be considered O(N) in the worst case.

Edge Cases:

• Empty Tree:
  • If the root is None, the function returns None without any processing.
• Single Node Tree:
  • If the tree contains only the root node, the root's value is set to 0 and returned.
• Unbalanced Tree:
  • The code correctly handles unbalanced trees because the level-order traversal ensures that cousins are accurately identified at each level.
• Nodes with Null Children:
  • The code considers None children when computing the cousin_sum.