2641. Cousins in Binary Tree II - Detailed Explanation

Problem Statement

Given the root of a binary tree, update the tree so that for every node (except the root) its new value becomes the sum of all values of nodes on the same level excluding the node’s siblings (i.e. nodes sharing the same parent). For the root, set the value to 0.

Example 1

• Input:
  A binary tree represented as:

         5
       /   \
      4     9
     / \   / \
    1  10  7   3
  

• Output:
  The modified tree becomes:

         0
       /   \
      0     0
     / \   / \
   10  10 11  11
  

• Explanation:
  • The root (5) becomes 0.
  • Level 1: Nodes 4 and 9 are siblings. The total at level 1 is 4 + 9 = 13; however, since each node’s “siblings sum” equals the level sum, both become 13 − 13 = 0.
  • Level 2:
    • For node 1 and its sibling 10 (children of 4), the level sum is 1 + 10 + 7 + 3 = 21. Their parent’s children sum is 1 + 10 = 11, so each becomes 21 − 11 = 10.
    • For node 7 and 3 (children of 9), the parent’s children sum is 7 + 3 = 10, so each becomes 21 − 10 = 11.

Example 2

• Input:

         1
       /   \
      2     3
  

• Output:

         0
       /   \
      0     0
  

• Explanation:
  • Level 0: Root 1 → 0.
  • Level 1: Nodes 2 and 3 are siblings; level sum = 2 + 3 = 5, and their parent’s sum is 5. So both become 5 − 5 = 0.

Example 3

• Input: A single-node tree:

    7
  

• Output:

    0
  

• Explanation:
  There are no cousins for the only node, so it becomes 0.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁵].
• Node values can be any integer.
• The tree is given in a standard binary tree format (each node has at most two children).

Hints

1. Level Order Traversal:
   Think about using breadth-first search (BFS) to traverse the tree level by level. This way, you can compute the total sum of values at each level easily.

2. Sibling Exclusion:
   For a node (other than the root), note that its “cousin sum” is simply the total sum at its level minus the sum of its siblings (i.e. the children of its parent). Be sure to calculate these sums using the original values before any are replaced.

Approaches

1. Brute Force Approach

Idea:
For each node (except the root), perform a separate level order traversal to find all nodes at the same level, then subtract the sum of the node’s siblings.

Steps:

• For every node, run a level order traversal to compute the level sum.
• Find the parent of the node and compute the sum of values of all its children.
• Set the node’s new value = (level sum) − (sum of the node’s siblings, including itself).

Drawbacks:

• This approach repeats work (traversing levels multiple times).
• It leads to an inefficient solution (O(n²) time in the worst case), which is not practical for large trees.

2. Optimal Approach Using a Single BFS Traversal

Idea:
Perform one level order traversal (using BFS) and for each level, do the following:

• Compute the total sum of values at that level.
• For each parent in that level, compute the sum of its children (using the original node values).
• For every child node, update its value to be (total level sum) minus (the sum of its own siblings, which is the sum of children of its parent).

Steps:

1. Use a queue to perform BFS on the tree.
2. For each level:
   • First, compute the level_sum of all nodes.
   • Then, for each node in that level, if it has children, record the sum of its children.
   • In the next iteration (or by using an auxiliary structure), assign each child’s new value as:
     new_value(child) = level_sum (of child’s level) − (sum of children of its parent)
3. Special case: For the root node, set its value to 0.

Benefits:

• Only one traversal of the tree (O(n) time).
• Uses extra space to store sums per level and per parent (O(n) space).

Code Implementation

Python Code