2641. Cousins in Binary Tree II LeetCode Solution

In this guide, you will get 2641. Cousins in Binary Tree II LeetCode Solution with the best time and space complexity. The solution to Cousins in Binary Tree II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Cousins in Binary Tree II solution in C++
Cousins in Binary Tree II solution in Java
Cousins in Binary Tree II solution in Python
Additional Resources

2641. Cousins in Binary Tree II LeetCode Solution image

Problem Statement of Cousins in Binary Tree II

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2641. Cousins in Binary Tree II LeetCode Solution in C++

class Solution {
 public:
  TreeNode* replaceValueInTree(TreeNode* root) {
    vector<int> levelSums;
    dfs(root, 0, levelSums);
    return replace(root, 0, new TreeNode(0), levelSums);
  }

 private:
  void dfs(TreeNode* root, int level, vector<int>& levelSums) {
    if (root == nullptr)
      return;
    if (levelSums.size() == level)
      levelSums.push_back(0);
    levelSums[level] += root->val;
    dfs(root->left, level + 1, levelSums);
    dfs(root->right, level + 1, levelSums);
  }

  TreeNode* replace(TreeNode* root, int level, TreeNode* curr,
                    const vector<int>& levelSums) {
    const int nextLevel = level + 1;
    const int nextLevelCousinsSum =
        nextLevel >= levelSums.size()
            ? 0
            : levelSums[nextLevel] -
                  (root->left == nullptr ? 0 : root->left->val) -
                  (root->right == nullptr ? 0 : root->right->val);
    if (root->left != nullptr) {
      curr->left = new TreeNode(nextLevelCousinsSum);
      replace(root->left, level + 1, curr->left, levelSums);
    }
    if (root->right != nullptr) {
      curr->right = new TreeNode(nextLevelCousinsSum);
      replace(root->right, level + 1, curr->right, levelSums);
    }
    return curr;
  }
};
/* code provided by PROGIEZ */

2641. Cousins in Binary Tree II LeetCode Solution in Java

class Solution {
  public TreeNode replaceValueInTree(TreeNode root) {
    List<Integer> levelSums = new ArrayList<>();
    dfs(root, 0, levelSums);
    return replace(root, 0, new TreeNode(0), levelSums);
  }

  private void dfs(TreeNode root, int level, List<Integer> levelSums) {
    if (root == null)
      return;
    if (levelSums.size() == level)
      levelSums.add(0);
    levelSums.set(level, levelSums.get(level) + root.val);
    dfs(root.left, level + 1, levelSums);
    dfs(root.right, level + 1, levelSums);
  }

  private TreeNode replace(TreeNode root, int level, TreeNode curr, List<Integer> levelSums) {
    final int nextLevel = level + 1;
    final int nextLevelCousinsSum = nextLevel >= levelSums.size()
                                        ? 0
                                        : levelSums.get(nextLevel) -
                                              (root.left == null ? 0 : root.left.val) -
                                              (root.right == null ? 0 : root.right.val);
    if (root.left != null) {
      curr.left = new TreeNode(nextLevelCousinsSum);
      replace(root.left, level + 1, curr.left, levelSums);
    }
    if (root.right != null) {
      curr.right = new TreeNode(nextLevelCousinsSum);
      replace(root.right, level + 1, curr.right, levelSums);
    }
    return curr;
  }
}
// code provided by PROGIEZ

2641. Cousins in Binary Tree II LeetCode Solution in Python

class Solution:
  def replaceValueInTree(self, root: TreeNode | None) -> TreeNode | None:
    levelSums = []

    def dfs(root: TreeNode | None, level: int) -> None:
      if not root:
        return
      if len(levelSums) == level:
        levelSums.append(0)
      levelSums[level] += root.val
      dfs(root.left, level + 1)
      dfs(root.right, level + 1)

    def replace(
        root: TreeNode | None,
        level: int, curr: TreeNode | None,
    ) -> TreeNode | None:
      nextLevel = level + 1
      nextLevelCousinsSum = (
          (levelSums[nextLevel] if nextLevel < len(levelSums) else 0) -
          (root.left.val if root.left else 0) -
          (root.right.val if root.right else 0))
      if root.left:
        curr.left = TreeNode(nextLevelCousinsSum)
        replace(root.left, level + 1, curr.left)
      if root.right:
        curr.right = TreeNode(nextLevelCousinsSum)
        replace(root.right, level + 1, curr.right)
      return curr

    dfs(root, 0)
    return replace(root, 0, TreeNode(0))
 # code by PROGIEZ