Cousins in Binary Tree II Solution in Python

Problem Description

So, you think you know your family tree? Well, think again! In the world of binary trees, cousins are not just those awkward relatives you see at family reunions. In this problem, we need to find the cousins of a node in a binary tree, but with a twist! Instead of just identifying them, we need to replace each node’s value with the sum of its cousins’ values. Yes, you heard that right! It’s like a family reunion where everyone shares their candy, but only the cousins get to keep the loot!

Imagine you have a family tree where each node represents a family member. The cousins are those who are on the same level but are not siblings. Your task is to replace each node’s value with the sum of its cousins’ values. If a node has no cousins, it gets a value of zero.

Code Solution


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))

Approach Explanation

The solution employs a depth-first search (DFS) strategy to traverse the binary tree. First, we calculate the sum of values at each level of the tree using the dfs function. This gives us a list of sums for each level, which we store in levelSums.

Next, we use another function, replace, to traverse the tree again and replace each node's value with the sum of its cousins' values. We calculate the cousin sum by subtracting the values of the current node's children from the total sum of the next level. This ensures that we only consider the cousins and not the siblings.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of nodes in the binary tree.
Space Complexity	O(H), where H is the height of the tree.

Real-World Example

Think of a family reunion where each cousin brings a different dish. If one cousin brings a pie worth $10 and another brings a cake worth $15, the total value of the cousins' contributions is $25. Now, if you were to replace the value of each cousin with the total value of all the other cousins' contributions, it would be like saying, "Hey, your pie is now worth $15 (the cake) and the cake is worth $10 (the pie)." This is essentially what our algorithm does, but in the binary tree world!