{x}
blog image

Sum of Nodes with Even-Valued Grandparent

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

 

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Input: root = [1]
Output: 0

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 1 <= Node.val <= 100

1315. Sum of Nodes with Even-Valued Grandparent

Problem Description

Given the root of a binary tree, calculate the sum of the values of all nodes that have an even-valued grandparent. A grandparent is defined as the parent of a node's parent. If no nodes have an even-valued grandparent, return 0.

Approach: Depth-First Search (DFS)

The most efficient way to solve this problem is using a Depth-First Search (DFS) approach. We'll recursively traverse the tree, keeping track of the parent's value and the grandparent's value.

Algorithm:

  1. Base Case: If the current node is null, return 0.

  2. Recursive Step: Recursively call the DFS function on the left and right subtrees.

  3. Grandparent Check: If the grandparent's value (passed as an argument) is even, add the current node's value to the sum.

  4. Parent Update: Pass the current node's value as the new parent value for the recursive calls on its children.

  5. Return: Return the accumulated sum.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In a balanced tree, H is log₂(N).

Code Implementation (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(node, parent_val, grandparent_val):
            if not node:
                return 0
            
            total_sum = dfs(node.left, node.val, parent_val) + dfs(node.right, node.val, parent_val)
 
            if grandparent_val % 2 == 0:
                total_sum += node.val
            
            return total_sum
 
        return dfs(root, 0, 0) #Initial parent and grandparent values are 0

Code Implementation (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return dfs(root, 0, 0);
    }
 
    private int dfs(TreeNode node, int parentVal, int grandparentVal) {
        if (node == null) {
            return 0;
        }
 
        int sum = dfs(node.left, node.val, parentVal) + dfs(node.right, node.val, parentVal);
 
        if (grandparentVal % 2 == 0) {
            sum += node.val;
        }
 
        return sum;
    }
}

Code Implementation (C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumEvenGrandparent(TreeNode* root) {
        return dfs(root, 0, 0);
    }
 
    int dfs(TreeNode* node, int parentVal, int grandparentVal) {
        if (!node) return 0;
 
        int sum = dfs(node->left, node->val, parentVal) + dfs(node->right, node->val, parentVal);
        if (grandparentVal % 2 == 0) sum += node->val;
        return sum;
    }
};

The implementations in other languages (JavaScript, Go, TypeScript etc.) would follow a very similar structure, adapting the syntax and data structures specific to that language. The core algorithm remains the same.