Cousins in Binary Tree II Solution in C++

Problem Description

Welcome to the world of binary trees, where every node has a family tree that would make even the most complicated soap opera look simple! In the “Cousins in Binary Tree II” problem, we are tasked with replacing each node’s value with the sum of all its cousins’ values. Yes, you heard that right! If you thought family reunions were awkward, just wait until you see how these nodes interact.

Imagine a family gathering where everyone is trying to figure out how much money their cousins have. Instead of asking directly, they just add up all the cousins’ wealth and replace their own value with that sum. So, if Cousin A has $10, Cousin B has $20, and Cousin C has $30, Cousin D will replace their value with $60. Sounds like a fun family reunion, right?

Code Solution


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

 private:
  void dfs(TreeNode* root, int level, vector& 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& 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;
  }
};

Approach Explanation

The approach taken in this solution is a two-step process:

Depth-First Search (DFS): We traverse the tree to calculate the sum of values at each level. This is stored in a vector called levelSums.
Replacement: We then traverse the tree again, replacing each node’s value with the sum of its cousins’ values, which we calculate using the levelSums vector.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. We traverse each node twice: once for calculating sums and once for replacing values.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack used during the DFS.

Real-World Example

Think of a family reunion where each cousin is trying to figure out how much money they have compared to their cousins. Instead of asking each other, they just look at the total wealth of their cousins and adjust their own wealth accordingly. This is exactly what our binary tree nodes are doing! They are calculating the total wealth of their cousins (other nodes at the same level) and replacing their own value with that sum.