# Cousins in Binary Tree II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/cousins-in-binary-tree-ii)
Canonical: https://scaleengineer.com/dsa/problems/cousins-in-binary-tree-ii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/cousins-in-binary-tree-ii/image0.png) 

**Input:** root = [5,4,9,1,10,null,7]
**Output:** [0,0,0,7,7,null,11]
**Explanation:** The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- 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.

**Example 2:**

![](https://assets.glich.co/dsa/cousins-in-binary-tree-ii/image1.png) 

**Input:** root = [3,1,2]
**Output:** [0,0,0]
**Explanation:** The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 3 does not have any cousins so its sum is 0.
- Node with value 1 does not have any cousins so its sum is 0.
- Node with value 2 does not have any cousins so its sum is 0.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 105]`.
* `1 <= Node.val <= 104`

# Approaches
## Two-Pass Level-Order Traversal (BFS)
This approach solves the problem by breaking it down into two distinct phases: a data gathering phase and an update phase. It uses two separate Breadth-First Search (BFS) traversals. The first pass calculates and stores the sum of node values for each level in the tree. The second pass then uses this pre-computed information to calculate the sum of cousins for each node and update its value accordingly. The core formula used is: `cousin_sum = total_level_sum - siblings_sum`.
**Time:** O(N), where N is the number of nodes. We perform two separate traversals of the tree, and each traversal visits every node once. Thus, the complexity is O(N) + O(N) = O(N). · **Space:** O(N), where N is the number of nodes. The space is dominated by the BFS queue, which can hold up to N/2 nodes (the maximum width of the tree), and the `levelSums` map, which can store up to N entries in the case of a skewed tree.
**Pros:** The logic is separated into clear, understandable steps.; Relatively easy to implement and debug due to the separation of concerns.
**Cons:** Requires two full traversals of the tree.; Uses extra space for the `levelSums` map, which can be significant for deep trees.
### Explanation
The logic is straightforward. We first need to know the sum of values for every level in the tree. A BFS traversal is perfect for this. We traverse the tree level by level, and for each level, we sum up the values of all nodes and store it in a hash map, mapping the depth to the sum.

After populating the sums for all levels, we perform a second traversal. The root's value is set to 0. For any other node, its new value is the sum of all nodes at its level minus the sum of its own siblings. We can find the sum of its siblings by looking at their common parent. For a given `parent` node, the sum of its children's values (`siblingsSum`) is calculated. Then, for each child, its new value is the total sum of its level (which we fetched from our map) minus this `siblingsSum`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // Pass 1: Calculate sum of each level
        Map<Integer, Integer> levelSums = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int levelSize = q.size();
            int currentLevelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                currentLevelSum += node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            levelSums.put(depth, currentLevelSum);
            depth++;
        }

        // Pass 2: Update node values
        root.val = 0;
        q.offer(root);
        depth = 0;
        while (!q.isEmpty()) {
            int levelSize = q.size();
            int nextLevelSum = levelSums.getOrDefault(depth + 1, 0);
            for (int i = 0; i < levelSize; i++) {
                TreeNode parent = q.poll();
                int childrenSum = 0;
                if (parent.left != null) childrenSum += parent.left.val;
                if (parent.right != null) childrenSum += parent.right.val;

                if (parent.left != null) {
                    parent.left.val = nextLevelSum - childrenSum;
                    q.offer(parent.left);
                }
                if (parent.right != null) {
                    parent.right.val = nextLevelSum - childrenSum;
                    q.offer(parent.right);
                }
            }
            depth++;
        }

        return root;
    }
}
```
### Algorithm
- **Pass 1: Calculate Level Sums.**
  - Initialize a map, `levelSums`, to store the sum of node values for each depth.
  - Perform a Breadth-First Search (BFS) starting from the root.
  - For each level of the tree, calculate the sum of all node values at that level.
  - Store this sum in the `levelSums` map with the depth as the key.
- **Pass 2: Update Node Values.**
  - Set the root's value to 0, as it has no cousins.
  - Perform a second BFS traversal, again starting from the root.
  - For each node processed (let's call it `parent`) at depth `d`:
    - Calculate the sum of its immediate children's values (`siblingsSum`).
    - Retrieve the total sum for the next level (`d + 1`) from the `levelSums` map.
    - For each child of the `parent`, update its value to `(total sum of next level) - siblingsSum`.
- Return the modified root.

## Optimized Single-Pass Level-Order Traversal (BFS)
This optimized approach uses a single Breadth-First Search (BFS) traversal to modify the tree. Instead of a preliminary pass to gather level sums, it calculates the necessary information on the fly. At each level of the traversal, it first calculates the total sum of all nodes in the *next* level. With this sum, it then iterates through the current level's nodes again, calculates the sum of each node's direct children (siblings), and updates the children's values using the formula `cousin_sum = total_next_level_sum - siblings_sum`. This avoids a second full traversal and the need for an auxiliary map to store level sums.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued once. The nodes at each level are iterated over twice, but this is a constant factor. Therefore, the total time complexity is linear with respect to the number of nodes. · **Space:** O(N), where N is the number of nodes. The space is used for the BFS queue, which can store up to O(W) nodes, where W is the maximum width of the tree. In a complete binary tree, W can be N/2, leading to O(N) space.
**Pros:** More efficient in terms of time and space complexity constants by avoiding a second full traversal and an extra map.; Performs the entire operation in a single pass over the tree structure.
**Cons:** The logic within the main loop is slightly more complex as it involves multiple steps: calculating the next level's sum and then updating the children.; Requires a temporary data structure (like a list) to hold the nodes of the current level, adding a bit to the constant factor of space usage.
### Explanation
This method refines the two-pass approach into a single, more efficient pass. We still process the tree level by level using BFS. The key idea is that to update the values of nodes at level `d+1`, we only need information from level `d` (their parents) and the total sum of values at level `d+1`.

We start by setting the root's value to 0. Then, we begin our BFS. In each step of the while loop, we are processing a single level. We first drain the queue for the current level into a temporary list. This gives us all nodes at the current level. We then perform two sub-steps:
1. We iterate through this list of current-level nodes to calculate the sum of all their children's values. This sum is precisely the total sum of the next level.
2. We iterate through the list of current-level nodes a second time. For each `parent` node, we find the sum of its children (`siblingsSum`). We then update each child's value to `nextLevelSum - siblingsSum` and add the child to the queue for the next iteration.

This way, we compute the required sum and perform the update for the next level within the same main loop iteration, eliminating the need for a second pass.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        root.val = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int levelSize = q.size();
            List<TreeNode> currentLevelNodes = new ArrayList<>();
            int nextLevelSum = 0;

            // First, get all nodes for the current level and calculate the sum of the next level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll();
                currentLevelNodes.add(node);
                if (node.left != null) {
                    nextLevelSum += node.left.val;
                }
                if (node.right != null) {
                    nextLevelSum += node.right.val;
                }
            }

            // Second, update the children's values and enqueue them for the next level
            for (TreeNode parent : currentLevelNodes) {
                int childrenSum = 0;
                if (parent.left != null) {
                    childrenSum += parent.left.val;
                }
                if (parent.right != null) {
                    childrenSum += parent.right.val;
                }

                if (parent.left != null) {
                    parent.left.val = nextLevelSum - childrenSum;
                    q.offer(parent.left);
                }
                if (parent.right != null) {
                    parent.right.val = nextLevelSum - childrenSum;
                    q.offer(parent.right);
                }
            }
        }

        return root;
    }
}
```
### Algorithm
- Handle the edge case of a null or single-node tree. Set the root's value to 0.
- Initialize a queue for BFS and add the root to it.
- Begin a level-order traversal loop that continues as long as the queue is not empty.
- In each iteration of the loop, which corresponds to processing one level:
  - First, determine the size of the current level and create a temporary list to hold the nodes of this level.
  - Dequeue all nodes from the main queue and add them to the temporary list.
  - **Calculate Next Level's Sum:** Iterate through the nodes in the temporary list. For each node, sum the values of its children. This gives the total sum of values for the *next* level.
  - **Update Children's Values:** Iterate through the nodes in the temporary list again. For each `parent` node:
    - Calculate the sum of its own children's values (`siblingsSum`).
    - For each child of the `parent`, update its value to `(next level's sum) - siblingsSum`.
    - Enqueue the updated children into the main queue for the next level's processing.
- Return the modified root.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < Integer > s = new ArrayList <>(); public TreeNode replaceValueInTree ( TreeNode root ) { dfs1 ( root , 0 ); root . val = 0 ; dfs2 ( root , 1 ); return root ; } private void dfs1 ( TreeNode root , int d ) { if ( root == null ) { return ; } if ( s . size () <= d ) { s . add ( 0 ); } s . set ( d , s . get ( d ) + root . val ); dfs1 ( root . left , d + 1 ); dfs1 ( root . right , d + 1 ); } private void dfs2 ( TreeNode root , int d ) { if ( root == null ) { return ; } int l = root . left == null ? 0 : root . left . val ; int r = root . right == null ? 0 : root . right . val ; if ( root . left != null ) { root . left . val = s . get ( d ) - l - r ; } if ( root . right != null ) { root . right . val = s . get ( d ) - l - r ; } dfs2 ( root . left , d + 1 ); dfs2 ( root . right , d + 1 ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * replaceValueInTree ( TreeNode * root ) { vector < int > s ; function < void ( TreeNode * , int ) > dfs1 = [ & ]( TreeNode * root , int d ) { if ( ! root ) { return ; } if ( s . size () <= d ) { s . push_back ( 0 ); } s [ d ] += root -> val ; dfs1 ( root -> left , d + 1 ); dfs1 ( root -> right , d + 1 ); }; function < void ( TreeNode * , int ) > dfs2 = [ & ]( TreeNode * root , int d ) { if ( ! root ) { return ; } int l = root -> left ? root -> left -> val : 0 ; int r = root -> right ? root -> right -> val : 0 ; if ( root -> left ) { root -> left -> val = s [ d ] - l - r ; } if ( root -> right ) { root -> right -> val = s [ d ] - l - r ; } dfs2 ( root -> left , d + 1 ); dfs2 ( root -> right , d + 1 ); }; dfs1 ( root , 0 ); root -> val = 0 ; dfs2 ( root , 1 ); return root ; } };
```

### Python

```python
# 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 ]: def dfs1 ( root , d ): if root is None : return if len ( s ) <= d : s . append ( 0 ) s [ d ] += root . val dfs1 ( root . left , d + 1 ) dfs1 ( root . right , d + 1 ) def dfs2 ( root , d ): if root is None : return t = ( root . left . val if root . left else 0 ) + ( root . right . val if root . right else 0 ) if root . left : root . left . val = s [ d ] - t if root . right : root . right . val = s [ d ] - t dfs2 ( root . left , d + 1 ) dfs2 ( root . right , d + 1 ) s = [] dfs1 ( root , 0 ) root . val = 0 dfs2 ( root , 1 ) return root
```