Cousins in Binary Tree II

Medium
1962.

Cousins in Binary Tree II

Cousins in Binary Tree II is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon interviews.

You are given the root of a binary tree. Two nodes are cousins when they are on the same level (the same depth) but have different parents.

Replace the value of every node with the sum of the values of all its cousins, computed from the original values, and return the root of the modified tree. A node with no cousins gets 0.

Example 1

Input
root = [5,4,9,1,10,null,7]
Output
[0,0,0,7,7,null,11]
Explanation
The root and its two children have no cousins, so they become 0. On level 3, 1 and 10 have the cousin 7, and 7 has the cousins 1 and 10: they become 7, 7 and 11.

Example 2

Input
root = [3,1,2]
Output
[0,0,0]
Explanation
1 and 2 are siblings, not cousins, so every value becomes 0.

Example 3

Input
root = [1,2,3,4,5,6,7]
Output
[0,0,0,13,13,9,9]
Explanation
On level 3, 4 and 5 have the cousins 6 and 7 (sum 13); 6 and 7 have the cousins 4 and 5 (sum 9).

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var replaceValueInTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Cousins in Binary Tree II — Solution in Python, Java & C++

Cousins in Binary Tree II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Cousins in Binary Tree II is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Hash Table, Breadth-First Search, Trees
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary tree. Two nodes are cousins when they are on the same level (the same depth) but have different parents.

Replace the value of every node with the sum of the values of all its cousins, computed from the original values, and return the root of the modified tree. A node with no cousins gets 0.

Example 1

Input: root = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Explanation: The root and its two children have no cousins, so they become 0. On level 3, 1 and 10 have the cousin 7, and 7 has the cousins 1 and 10: they become 7, 7 and 11.

Example 2

Input: root = [3,1,2]
Output: [0,0,0]
Explanation: 1 and 2 are siblings, not cousins, so every value becomes 0.

Example 3

Input: root = [1,2,3,4,5,6,7]
Output: [0,0,0,13,13,9,9]
Explanation: On level 3, 4 and 5 have the cousins 6 and 7 (sum 13); 6 and 7 have the cousins 4 and 5 (sum 9).

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^4

Hints for Cousins in Binary Tree II

  1. Hint 1

    A node's cousins are all the nodes of its level except itself and its sibling.

  2. Hint 2

    So its new value is (the whole level's sum) minus (the sum of the children of its parent).

  3. Hint 3

    Go level by level: from each node of the current level you can see both its children, so compute the next level's total and each pair's sum before overwriting the children.

How to solve Cousins in Binary Tree II

The cousins of a node are its level minus its parent's children. With a breadth-first walk, standing on a level, compute the next level's total from the original child values, then set each child to that total minus its own sibling pair's sum.

Approach

  1. Set the root's value to 0 (it has no cousins) and start with the root as the current level.
  2. For each node of the current level, compute pair = the sum of its children's values; add every pair into nextTotal.
  3. Walk the current level again and set each child's value to nextTotal - pair of its parent; collect the children as the next level.
  4. Repeat until a level has no children, then return the root.

Why it works

All the sums on a level are taken before any child on that level is overwritten, so they use the original values. A child's sibling group is exactly its parent's children, so nextTotal - pair removes the child and its sibling and keeps every other node of the level — its cousins.

Complexity

  • Time — O(n)
  • Space — O(w), w the widest level

Pitfalls

  • Overwriting a child before the level's total is computed mixes new and old values; finish the sums first.
  • Siblings are not cousins — a node's own sibling must be left out of its sum, not just the node itself.

Reference solution

Python

from typing import Optional

def replaceValueInTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
    root.val = 0
    level = [root]
    while level:
        pairs = []
        total = 0
        for node in level:
            s = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
            pairs.append(s)
            total += s
        nxt = []
        for node, s in zip(level, pairs):
            for child in (node.left, node.right):
                if child:
                    child.val = total - s
                    nxt.append(child)
        level = nxt
    return root

Java

public static TreeNode replaceValueInTree(TreeNode root) {
    if (root == null) return null;
    root.val = 0;
    List<TreeNode> level = new ArrayList<>();
    level.add(root);
    while (!level.isEmpty()) {
        int m = level.size(), total = 0;
        int[] pairs = new int[m];
        for (int i = 0; i < m; i++) {
            TreeNode node = level.get(i);
            pairs[i] = (node.left != null ? node.left.val : 0) + (node.right != null ? node.right.val : 0);
            total += pairs[i];
        }
        List<TreeNode> next = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            TreeNode p = level.get(i);
            if (p.left != null) { p.left.val = total - pairs[i]; next.add(p.left); }
            if (p.right != null) { p.right.val = total - pairs[i]; next.add(p.right); }
        }
        level = next;
    }
    return root;
}

C++

TreeNode* replaceValueInTree(TreeNode* root) {
    if (!root) return nullptr;
    root->val = 0;
    vector<TreeNode*> level = {root};
    while (!level.empty()) {
        int m = (int) level.size(), total = 0;
        vector<int> pairs(m);
        for (int i = 0; i < m; i++) {
            TreeNode* node = level[i];
            pairs[i] = (node->left ? node->left->val : 0) + (node->right ? node->right->val : 0);
            total += pairs[i];
        }
        vector<TreeNode*> next;
        for (int i = 0; i < m; i++) {
            TreeNode* p = level[i];
            if (p->left) { p->left->val = total - pairs[i]; next.push_back(p->left); }
            if (p->right) { p->right->val = total - pairs[i]; next.push_back(p->right); }
        }
        level = next;
    }
    return root;
}

JavaScript

var replaceValueInTree = function(root) {
    if (root === null) return null;
    root.val = 0;
    var level = [root];
    while (level.length > 0) {
        var pairs = [], total = 0, i;
        for (i = 0; i < level.length; i++) {
            var node = level[i];
            var s = (node.left !== null ? node.left.val : 0) + (node.right !== null ? node.right.val : 0);
            pairs.push(s);
            total += s;
        }
        var next = [];
        for (i = 0; i < level.length; i++) {
            var p = level[i];
            if (p.left !== null) { p.left.val = total - pairs[i]; next.push(p.left); }
            if (p.right !== null) { p.right.val = total - pairs[i]; next.push(p.right); }
        }
        level = next;
    }
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Breadth-First Search (BFS)