Cousins in Binary Tree II

Cousins in Binary Tree II

What is this problem about?

The Cousins in Binary Tree II coding problem is a "Medium" variation where you are asked to transform the tree. For each node, you must replace its value with the sum of all its cousins' values. A cousin is defined as a node at the same depth with a different parent. If a node has no cousins, its new value should be 0.

Why is this asked in interviews?

Google and Amazon ask this binary tree interview pattern to test your ability to perform multi-pass tree manipulations. It requires calculating level-wide sums and then subtracting sibling values to isolate cousin values. It evaluates your proficiency with Breadth-First Search (BFS) and level-order data aggregation.

Algorithmic pattern used

This problem is best solved using a Two-Pass BFS.

1. Pass 1: Calculate the total sum of node values for each level of the tree. Store these sums in an array or map.
2. Pass 2: Perform another BFS. For a node at level $d$, its "cousin sum" is: (Total sum of level d) - (Sum of values of this node and its siblings).
3. Update the node values in-place or create a new tree.

Example explanation

Level 2 nodes: A(val 10, parent P1), B(val 20, parent P1), C(val 30, parent P2).

1. Total sum for Level 2 = $10 + 20 + 30 = 60$.
2. For A and B (siblings): Their sibling sum is $10 + 20 = 30$.
   • A's new value = $60 - 30 = 30$.
   • B's new value = $60 - 30 = 30$.
3. For C: Its sibling sum is just its own value (30).
   • C's new value = $60 - 30 = 30$.

Common mistakes candidates make

• Root Node: Forgetting that the root node (level 0) and its children (level 1) never have cousins, so their values should always become 0.
• Efficiency: Trying to find cousins for each node individually (O(N^2)) instead of using the "Level Sum - Sibling Sum" optimization (O(N)).
• Sibling Logic: Not correctly grouping children of the same parent during the second pass.

Interview preparation tip

When a problem asks for "all nodes in level EXCEPT siblings," the formula (Level Total) - (Sibling Total) is a very powerful optimization that avoids searching for individual cousins.