Sum Of Nodes With Even Valued Grandparent - Leetcode Solution

Problem Statement:

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

Solution:

Approach:

In this problem, we have to find a sum of nodes with even-valued grandparent, It means we have to go down to every level of the binary tree and check if the value of the grandparent node is even. If it is, then we have to add the values of its children nodes to our result. So, we will use a depth-first search algorithm to traverse through the tree and calculate the sum recursively.

Algorithm:

1. Initialize a variable sum with 0.
2. Traverse the tree recursively using Depth-First-Search (DFS).
3. For each node n, check if its grandparent grand_parent is an even number. If it is an even number, add the value of the current node n to the sum.
4. Traverse through the left subtree and the right subtree of the current node n recursively.
5. Return the final value of the sum.

Code:

In Python, we can implement the above algorithm as follows:

class Solution: def sumEvenGrandparent(self, root: TreeNode) -> int: sum = 0 def dfs(node, grand_parent, parent): nonlocal sum if not node: return if grand_parent and grand_parent.val % 2 == 0: sum += node.val dfs(node.left, parent, node) dfs(node.right, parent, node) dfs(root, None, None) return sum

The time complexity of the above algorithm is O(N), where N is the number of nodes in the binary tree. This is because we are traversing every node of the tree exactly once. The space complexity of the algorithm is O(H), where H is the height of the tree. This is because the maximum number of recursive calls that can be stored in the call stack depends on the height of the tree.

1