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 <= 104In #2641 Cousins in Binary Tree II, the goal is to replace each node’s value with the sum of values of all its cousins. Two nodes are cousins if they are on the same depth but have different parents. The key idea is to process the tree level by level and track the total value of nodes at each depth.
A common approach uses Breadth-First Search (BFS). For every level, compute the sum of all node values. Then for each parent node, subtract the values of its own children from the level sum to determine the cousin sum for those children. Update the child nodes accordingly.
An alternative implementation uses Depth-First Search (DFS) to first compute level sums and then update nodes in a second traversal. Both strategies rely on efficiently tracking level-based information using structures like queues or hash maps.
The overall solution runs in linear time since each node is visited a constant number of times.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS Level Order Traversal | O(n) | O(n) |
| DFS with Level Sum Tracking | O(n) | O(n) |
Techdose
Use these hints if you're stuck. Try solving on your own first.
Use DFS two times.
For the first time, find the sum of values of all the levels of the binary tree.
For the second time, update the value of the node with the sum of the values of the current level - sibling node’s values.
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.
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.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left, right;
6 TreeNode
This Java solution makes use of a breadth-first search (BFS) strategy using a queue to effectively traverse the tree by level. The tree nodes are then updated by computing the sum of cousins for each node.
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.
Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the tree.
1#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void replaceWithCousinsSumDFS(TreeNode* root, unordered_map<int, vector<int>>& levelSum, int depth) {
if (!root) return;
// Implement DFS with hash map logic
}
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(9);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(10);
root->right->right = new TreeNode(7);
unordered_map<int, vector<int>> levelSum;
replaceWithCousinsSumDFS(root, levelSum, 0);
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary tree transformation and level-based problems are common in FAANG-style interviews. While this exact problem may vary, similar questions involving BFS, DFS, and tree level sums frequently appear in coding interviews.
A queue is typically used to perform BFS level-order traversal of the binary tree. Additionally, some implementations use a hash map or array to store level sums when using a DFS-based solution.
The optimal approach is a level-order traversal using BFS. For each level, compute the total sum of node values and subtract sibling sums to update each node with the sum of its cousins. This allows the tree to be processed in linear time.
Yes, a DFS approach can be used by first calculating the sum of nodes at each depth and storing them in a map. A second DFS traversal then updates each node using the precomputed level sums while excluding sibling contributions.
In the C++ method, we utilize a DFS approach combined with an unordered map to associate depth levels with nodes, facilitating cousin sum calculation to adjust tree values.