Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Cousins in Binary Tree II solution and explanation

MediumBinary TreeBreadth-First SearchDepth-First SearchHash Table8 min read75.8% acceptanceUpdated 9 Apr 2026
Asked atAmazonGoogle
Practise Cousins in Binary Tree II
35:35
Cousins in Binary Tree II | 2 Detailed Approaches | Dry Run | Leetcode 2641 | codestorywithMIKcodestorywithMIK · 35:35 · 11K viewsWatch on YouTube
9 more videos on this problem
  1. Cousins in Binary Tree II | 2 Detailed Approaches | Dry Run | Leetcode 2641 | codestorywithMIKcodestorywithMIK · 35:35 · 11K views
  2. Cousins in Binary Tree II - Leetcode 2641 - PythonNeetCodeIO · 11:41 · 10K views
  3. 2641. Cousins in Binary Tree II | Leetcode Daily Challenge | DSA | Java | FAANGShashCode · 25:28 · 2K views
  4. Cousins in Binary Tree II | Leetcode 2641Techdose · 11:21 · 2K views
  5. 2641. Cousins in Binary Tree II C++ solution #leetcodeCodeQuest · 19:44 · 915 views
  6. Cousins in Binary Tree II | LeetCode 2641 in java | top DSA interview question | Must do Binary TreeCode Thoughts · 18:57 · 775 views
  7. Cousins in Binary Tree II - Binary Tree - DFS - Leetcode 2641 - PythonCheatCode Ninja · 7:32 · 600 views
  8. 2641. Cousins in Binary Tree II (Leetcode Medium)Programming Live with Larry · 6:54 · 457 views
  9. Daily Leetcode #1667: Oct 23, 2024 - 2641. Cousins in Binary Tree IIProgramming Live with Larry · 9:22 · 373 views
  10. Cousins in Binary Tree II - Leetcode 2641 - PythonAlgorithms Casts · 12:44 · 274 views

The 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:

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.

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def replace_with_cousins_sum(root):
    if not root:
        return None
    # Implement BFS to modify the tree
    return root

if __name__ == '__main__':
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(9)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(10)
    root.right.right = TreeNode(7)
    replace_with_cousins_sum(root)
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode replaceWithCousinsSum(TreeNode root) {
        if (root == null) return null;
        // Implement BFS and update tree
        return root;
    }

    public static void main(String[] args) {
        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);
        Solution sol = new Solution();
        sol.replaceWithCousinsSum(root);
    }
}
#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* replaceWithCousinsSum(TreeNode* root) {
    if (!root) return root;
    // Implement BFS and update root
    return root;
}

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);
    root = replaceWithCousinsSum(root);
    return 0;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function replaceWithCousinsSum(root) {
    if (root === null) return null;
    // Implement BFS
    return root;
}

const 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);
replaceWithCousinsSum(root);
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void modifyTree(struct TreeNode* root) {
    if (!root) return;
    // Implement BFS to modify the tree
    // Placeholder for the actual logic
}

int main() {
    struct TreeNode* root = createNode(5);
    root->left = createNode(4);
    root->right = createNode(9);
    root->left->left = createNode(1);
    root->left->right = createNode(10);
    root->right->right = createNode(7);
    modifyTree(root);
    return 0;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left; 
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode ReplaceWithCousinsSum(TreeNode root) {
        if (root == null) return root;
        // Implement BFS
        return root;
    }

    public static void 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);
        Solution sol = new Solution();
        sol.ReplaceWithCousinsSum(root);
    }
}

This Python solution employs a breadth-first search technique using a queue from the collections module to keep track of each node level. The node values are then modified according to the cousin sum calculation.

Complexity

Time Complexity: O(N)
Space Complexity: O(W)

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.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def dfs(node, levelSum, depth):
    if not node:
        return
    # Implement DFS with dictionary logic

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(1)
root.left.right = TreeNode(10)
root.right.right = TreeNode(7)
levelSum = {}
dfs(root, levelSum, 0)
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public void dfs(TreeNode node, Map<Integer, List<Integer>> levelSum, int depth) {
        if (node == null) return;
        // Implement DFS with map logic
    }

    public static void main(String[] args) {
        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);
        Solution sol = new Solution();
        Map<Integer, List<Integer>> levelSum = new HashMap<>();
        sol.dfs(root, levelSum, 0);
    }
}
#include <iostream>
#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;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function dfs(node, levelSum, depth) {
    if (node === null) return;
    // Implement DFS with depth tracking logic
}

const 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);
const levelSum = {};
dfs(root, levelSum, 0);
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void modifyTreeDFS(struct TreeNode* root) {
    if (!root) return;
    // Implement DFS to modify the tree
    // Placeholder for the actual logic
}

int main() {
    struct TreeNode* root = createNode(5);
    root->left = createNode(4);
    root->right = createNode(9);
    root->left->left = createNode(1);
    root->left->right = createNode(10);
    root->right->right = createNode(7);
    modifyTreeDFS(root);
    return 0;
}
using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left; 
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public void DFS(TreeNode node, Dictionary<int, List<int>> levelSum, int depth) {
        if (node == null) return;
        // Implement DFS with dictionary logic
    }

    public static void 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);
        Solution sol = new Solution();
        Dictionary<int, List<int>> levelSum = new Dictionary<int, List<int>>();
        sol.DFS(root, levelSum, 0);
    }
}

The Python implementation uses depth-first search (DFS) with a dictionary to correlate nodes to their respective depth levels, computing cousin sums for tree values, which allows for efficient node updates.

Complexity

Time Complexity: O(N)
Space Complexity: O(H)

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.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function replaceValueInTree(root: TreeNode | null): TreeNode | null {
    const s: number[] = [];
    const dfs1 = (root: TreeNode | null, depth: number) => {
        if (!root) {
            return;
        }
        if (s.length <= depth) {
            s.push(0);
        }
        s[depth] += root.val;
        dfs1(root.left, depth + 1);
        dfs1(root.right, depth + 1);
    };
    const dfs2 = (root: TreeNode | null, depth: number) => {
        const sub = (root.left?.val || 0) + (root.right?.val || 0);
        ++depth;
        if (root.left) {
            root.left.val = s[depth] - sub;
            dfs2(root.left, depth);
        }
        if (root.right) {
            root.right.val = s[depth] - sub;
            dfs2(root.right, depth);
        }
    };
    dfs1(root, 0);
    root.val = 0;
    dfs2(root, 0);
    return root;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func replaceValueInTree(root *TreeNode) *TreeNode {
	s := []int{}
	var dfs1 func(*TreeNode, int)
	dfs1 = func(root *TreeNode, depth int) {
		if root == nil {
			return
		}
		if len(s) <= depth {
			s = append(s, 0)
		}
		s[depth] += root.Val
		dfs1(root.Left, depth+1)
		dfs1(root.Right, depth+1)
	}
	var dfs2 func(*TreeNode, int)
	dfs2 = func(root *TreeNode, depth int) {
		l, r := 0, 0
		if root.Left != nil {
			l = root.Left.Val
		}
		if root.Right != nil {
			r = root.Right.Val
		}
		sub := l + r
		depth++
		if root.Left != nil {
			root.Left.Val = s[depth] - sub
			dfs2(root.Left, depth)
		}
		if root.Right != nil {
			root.Right.Val = s[depth] - sub
			dfs2(root.Right, depth)
		}
	}
	dfs1(root, 0)
	root.Val = 0
	dfs2(root, 0)
	return root
}
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.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function replaceValueInTree(root: TreeNode | null): TreeNode | null {
    let q = [root];
    let [sum, nextSum] = [0, root.val];

    while (q.length) {
        const qNext: TreeNode[] = [];
        [sum, nextSum] = [nextSum, 0];

        for (const node of q) {
            const x = (node.left?.val ?? 0) + (node.right?.val ?? 0);
            node.val = sum - node.val;
            nextSum += x;

            if (node.left) {
                node.left.val = x;
                qNext.push(node.left);
            }

            if (node.right) {
                node.right.val = x;
                qNext.push(node.right);
            }
        }

        q = qNext;
    }

    return root;
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func replaceValueInTree(root *TreeNode) *TreeNode {
	root.Val = 0
	q := []*TreeNode{root}
	for len(q) > 0 {
		t := []*TreeNode{}
		s := 0
		for _, node := range q {
			if node.Left != nil {
				t = append(t, node.Left)
				s += node.Left.Val
			}
			if node.Right != nil {
				t = append(t, node.Right)
				s += node.Right.Val
			}
		}
		for _, node := range q {
			sub := 0
			if node.Left != nil {
				sub += node.Left.Val
			}
			if node.Right != nil {
				sub += node.Right.Val
			}
			if node.Left != nil {
				node.Left.Val = s - sub
			}
			if node.Right != nil {
				node.Right.Val = s - sub
			}
		}
		q = t
	}
	return root
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Breadth-First Search with Level Tracking

Time Complexity: O(N)
Space Complexity: O(W)

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

Time Complexity: O(N)
Space Complexity: O(H)

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

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.

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.

Comments

Next problem · similarCousins in Binary TreeEasy
Now write it yourselfClose this page and solve Cousins in Binary Tree II in the editor, without looking.
Practise Cousins in Binary Tree II