Cousins in Binary Tree II Solution in Java

Explore Solutions in Other Languages

Problem Description

Welcome to the whimsical world of binary trees, where nodes are like distant relatives at a family reunion—some are close, and some are just… well, cousins! The problem at hand is to transform a binary tree such that each node’s value is replaced by the sum of all its cousins’ values. Yes, you heard that right! If you thought family gatherings were complicated, try keeping track of cousin values in a binary tree!

Imagine you have a family tree where each node represents a family member. The challenge is to ensure that every family member (node) knows how much their cousins (nodes at the same level) are worth. So, if Uncle Bob has a value of 5 and Aunt Sally has a value of 10, their kids (the cousins) should know that their combined worth is 15. But wait, if they have siblings, they need to subtract their own value from that total. Talk about family drama!

Code Solution


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

  private void dfs(TreeNode root, int level, List 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 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;
  }
}

Approach Explanation

The solution employs a depth-first search (DFS) strategy to traverse the binary tree. First, it calculates the sum of values at each level of the tree using the dfs method. This sum is stored in a list called levelSums. Then, the replace method is called to create a new tree where each node’s value is replaced by the sum of its cousins’ values. The key here is to ensure that each node subtracts its own value from the total cousin sum, ensuring accuracy in the final values.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of nodes in the tree. Each node is visited once during the DFS traversal.
Space Complexity	O(H), where H is the height of the tree. This space is used for the recursion stack during the DFS.

Real-World Example

Think of a family reunion where everyone is trying to figure out how much money they collectively have. Each cousin (node) needs to know how much their other cousins (nodes at the same level) are worth, but they can’t include their own allowance (value). This problem is akin to calculating the total family wealth without counting your own contributions.