To solve Cousins in Binary Tree II, traverse the tree while tracking depth and parent for each node. Use two DFS passes: the first to aggregate sibling sums per level and the second to assign each node its cousins' total. This approach ensures O(n) time and handles missing or single-parent nodes without errors.
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.
How GhostInterview Helps
- Automatically tracks depth and parent information to avoid manual bookkeeping errors.
- Generates DFS traversal templates with sibling sum calculations included.
- Highlights edge cases where nodes have no cousins, ensuring correct updates.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Cousins in Binary Tree II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Cousins in Binary Tree II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The problem asks to calculate the number of minutes for an infection to spread across all nodes in a binary tree starting from a given node.
Open problem page#2458 Height of Binary Tree After Subtree Removal QueriesCompute the height of a binary tree efficiently after removing subtrees, using traversal and precomputed node state tracking.
Open problem page#2368 Reachable Nodes With RestrictionsIn the 'Reachable Nodes With Restrictions' problem, find the maximum reachable nodes from node 0 in a tree while avoiding restricted nodes.
Open problem page