#2641

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Cousins in Binary Tree II

Replace each node in a binary tree with the sum of all its cousins by carefully tracking depth and parent relationships.

hash table tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, transform the tree so that each node's value becomes the sum of all its cousins' values. Two nodes are considered cousins if they exist at the same depth but have different parents. Nodes with no cousins should be updated to 0.

Return the root of the modified tree after performing the cousin-sum transformation. You must account for all nodes efficiently using a strategy that tracks depth and sibling relationships during traversal, while respecting the tree's structure and constraints.

Examples

Example 1

Input: root = [5,4,9,1,10,null,7]

Output: [0,0,0,7,7,null,11]

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]

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

Solution Approach

First DFS to collect level sums

Traverse the tree depth-first, recording both the total sum of node values at each depth and the sum of sibling groups. Store this information in a Hash Table keyed by depth and parent reference.

Second DFS to assign cousin sums

Perform a second DFS where each node's new value is calculated as the level sum minus the sum of its siblings, effectively assigning the total of its cousins. Update the node values in place.

Handle edge cases and constraints

Ensure that nodes with no cousins are set to 0, handle null children correctly, and confirm all operations respect the O(n) time and space constraints for large trees up to 10^5 nodes.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The algorithm runs in O(n) time because each DFS visits every node once, and O(n) space is used to store level and sibling sums for all nodes. This avoids repeated traversal or recomputation.

What Interviewers Usually Probe

Look for depth and parent tracking in your solution.
Hash Table usage to store per-level sums is expected.
Consider two-pass DFS instead of recomputing cousin sums repeatedly.

Common Pitfalls or Variants

Common pitfalls

Failing to subtract sibling sums when calculating cousins, leading to incorrect node values.
Ignoring nodes with no cousins and not setting their value to 0.
Using a single DFS without tracking parents may mix up cousin calculations.

Follow-up variants

Compute product instead of sum of cousins per node.
Return a list of cousin sums instead of modifying the tree in place.
Limit cousin sums to nodes with exactly two cousins at each level.

FAQ

What defines a cousin in 'Cousins in Binary Tree II'?

Two nodes are cousins if they are at the same depth in the tree but have different parents.

Can a node with no cousins appear in the output?

Yes, any node without cousins must be updated to 0 in the transformed tree.

Why are two DFS traversals used in this problem?

The first DFS collects level and sibling sums, and the second assigns cousin sums, avoiding repeated recomputation.

What is the time complexity of the cousin sum transformation?

The algorithm runs in O(n) time since each node is visited twice and all operations per node are constant time.

How does using a Hash Table help in this pattern?

Hash Tables store level sums and sibling sums efficiently, allowing quick lookup when calculating each node's cousin value.

terminal

Solution

Solution 1: 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$).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs1(root: Optional[TreeNode], depth: int):
            if root is None:
                return
            if len(s) <= depth:
                s.append(0)
            s[depth] += root.val
            dfs1(root.left, depth + 1)
            dfs1(root.right, depth + 1)

        def dfs2(root: Optional[TreeNode], depth: int):
            sub = (root.left.val if root.left else 0) + (
                root.right.val if root.right else 0
            )
            depth += 1
            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)

        s = []
        dfs1(root, 0)
        root.val = 0
        dfs2(root, 0)
        return root

Solution 2: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs1(root: Optional[TreeNode], depth: int):
            if root is None:
                return
            if len(s) <= depth:
                s.append(0)
            s[depth] += root.val
            dfs1(root.left, depth + 1)
            dfs1(root.right, depth + 1)

        def dfs2(root: Optional[TreeNode], depth: int):
            sub = (root.left.val if root.left else 0) + (
                root.right.val if root.right else 0
            )
            depth += 1
            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)

        s = []
        dfs1(root, 0)
        root.val = 0
        dfs2(root, 0)
        return root

Continue Practicing

#2385 amount of time for binary tree to be infected #2458 height of binary tree after subtree removal queries #2368 reachable nodes with restrictions