Skip to main content
Talentd

Cousins in Binary Tree II - Solution & Explanation

MediumHash TableTreeDepth-First SearchBreadth-First Search26 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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, 105].
  • 1 <= Node.val <= 104

Approach Overview

Problem 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.

Approach 1: Approach 1: Breadth-First Search with Level Tracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Depth-First Search with HashMap for Cousin Tracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the tree.

Try this approach in the editor →

Approach 3: Two DFS Traversals

We create a list s to record the sum of the node values at each level of the binary tree, where s[depth] represents the sum of the node values at the depth-th level (the root node is at level 0).

Next, we perform a DFS traversal to calculate the values in the array s. Then, we perform another DFS traversal to update the values of each node's children. The value of a child node is equal to the sum of the node values at its level minus the value of the child node and its sibling nodes.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Breadth-First Search (BFS)

First, we update the root node's value to 0, and use a queue q to store all nodes at each level, initially enqueueing the root node.

Then, we traverse the queue, calculate the sum s of all child nodes' values at each level, then calculate the sum sub of each child node and its sibling nodes' values, and then update each child node's value to s - sub.

After the traversal ends, we return the root node.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(W), where W is the maximum width of the tree (number of nodes at the widest level) due to the queue.

Approach 2: Depth-First Search with HashMap for Cousin Tracking

Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the tree.

Two DFS Traversals—
Breadth-First Search (BFS)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search with Level TrackingO(n)O(n)Best general solution. Natural for computing level sums and updating cousin values.
Depth-First Search with HashMapO(n)O(n)Useful when you prefer recursive traversal or need depth-based aggregation using maps.

Video Solution

Cousins in Binary Tree II | 2 Detailed Approaches | Dry Run | Leetcode 2641 | codestorywithMIK • codestorywithMIK • 11,427 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Cousins in Binary Tree II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Cousins in Binary Tree

Next

Maximum Level Sum of a Binary Tree