Is Cousins in Binary Tree II easy or hard?

The problem is generally classified as Medium. The main challenge is recognizing that cousin sums depend on level totals and sibling subtraction. Once the level-sum idea is clear, the BFS implementation becomes straightforward.

How to solve Cousins in Binary Tree II in O(n)?

Traverse the tree level by level. For each level, compute the total sum of node values. Then for every parent, calculate the sum of its children and assign each child the value levelSum minus siblingSum. Since every node is processed once, the algorithm runs in O(n) time.

What is the best approach for Cousins in Binary Tree II?

The most practical approach uses breadth-first search with level tracking. Compute the sum of nodes at each level, then assign each child the value of levelSum minus the sum of its sibling group. This processes each node once, resulting in O(n) time and O(n) space complexity.

What data structure is used in Cousins in Binary Tree II?

The main data structures are a queue for breadth-first search and optionally a hash map for storing level sums in the DFS approach. The tree structure itself is a binary tree where each node contains references to left and right children.

What is the time complexity of Cousins in Binary Tree II?

Both the BFS and DFS solutions run in O(n) time because each node in the binary tree is visited a constant number of times. The space complexity is also O(n), either from the BFS queue storing a level of nodes or from recursion depth and a map storing level sums.

Cousins in Binary Tree II Python or Java solution approach?

In both Python and Java, the common implementation uses a queue for BFS. First compute the sum of nodes at the current level, then update child node values based on the total minus their sibling group sum. The logic is identical across languages with only syntax differences.

Is Cousins in Binary Tree II asked at Google, Amazon, or Meta?

Binary tree transformation and level-sum problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving BFS level traversal, cousin detection, and subtree aggregation are common interview patterns.

Description Hints 3 Solution Video 35:35

2641. Cousins in Binary Tree II

Medium75.8% acceptance2 companies

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:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁴

Asked at 2 companies

Amazon

Google

Topics

Hints open one at a time

Hint 1

Use DFS two times.

Hint 2

For the first time, find the sum of values of all the levels of the binary tree.

Hint 3

For the second time, update the value of the node with the sum of the values of the current level - sibling node’s values.

35:35

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution