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:
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:
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:
[1, 105].1 <= Node.val <= 104Problem Overview: Each node in the binary tree must be replaced with the sum of values of its cousins. Cousins are nodes on the same depth but with different parents. The root becomes 0, and every other node’s value becomes the total value of nodes at its level excluding itself and its sibling.
Approach 1: Breadth-First Search with Level Tracking (O(n) time, O(n) space)
This approach processes the tree level by level using breadth-first search. First compute the total sum of nodes at the current level. For each parent node, calculate the sum of its children (the sibling group). The cousin sum for each child becomes levelSum - siblingSum. Updating children this way ensures every node only includes values from nodes with different parents. The queue naturally separates nodes by depth, making it easy to compute level sums and propagate updates to the next level. This approach runs in O(n) time since every node is processed once, and it uses O(n) auxiliary space for the queue.
Approach 2: Depth-First Search with HashMap for Cousin Tracking (O(n) time, O(n) space)
This method performs two passes with depth-first search. The first DFS computes the sum of values at each depth and stores them in a HashMap<depth, sum>. The second DFS updates each node by subtracting the value of itself and its siblings from the stored depth sum. To do this efficiently, compute the combined value of the node’s sibling group before assigning new values to its children. The hash table enables constant-time lookup of the total sum for any depth. While DFS requires careful tracking of parent-child relationships, it avoids explicit level queues and works naturally for recursive tree traversal.
Recommended for interviews: The BFS level-order solution is usually the expected answer. It directly mirrors the problem definition—nodes grouped by depth—and keeps the logic easy to reason about during a whiteboard explanation. The DFS + HashMap variant demonstrates stronger understanding of tree traversal and state tracking across recursion, but the BFS approach is typically faster to implement under interview pressure.
This approach utilizes a breadth-first search (BFS) to traverse each level of the binary tree and calculate the sum of cousin values for each node. We maintain a queue to process each level separately and keep track of parent nodes to ensure calculations of cousins are accurate. This allows us to update the tree with the required values.
This solution uses a typical BFS approach to traverse the tree and calculate the value of cousins for each node. We can modify this to calculate the cousin sum and then update each node in the binary tree. For simplicity, the function `modifyTree` is a placeholder where we will implement the logic.
Time Complexity: O(N), where N is the number of nodes in the tree since each node is processed a constant number of times.
Space Complexity: O(W), where W is the maximum width of the tree (number of nodes at the widest level) due to the queue.
This approach leverages a depth-first search (DFS) strategy in combination with a hash map to keep track of nodes and their parents at each depth level. This allows easy computation of cousin sums to modify tree node values.
This solution in C uses depth-first traversal to explore each node in a binary tree and a hash map-like strategy (indicated in comments) to track the nodes and calculate the sum of cousins for tree nodes.
Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the tree.
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search with Level Tracking | Time Complexity: O(N), where N is the number of nodes in the tree since each node is processed a constant number of times. |
| Approach 2: Depth-First Search with HashMap for Cousin Tracking | Time Complexity: O(N) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search with Level Tracking | O(n) | O(n) | Best general solution. Natural for computing level sums and updating cousin values. |
| Depth-First Search with HashMap | O(n) | O(n) | Useful when you prefer recursive traversal or need depth-based aggregation using maps. |
Cousins in Binary Tree II | 2 Detailed Approaches | Dry Run | Leetcode 2641 | codestorywithMIK • codestorywithMIK • 10,723 views views
Watch 9 more video solutions →Practice Cousins in Binary Tree II with our built-in code editor and test cases.
Practice on FleetCode