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.

&nbsp;
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


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 104].
	1 &lt;= Node.val &lt;= 100


class Solution:
	def sumEvenGrandparent(self, root: TreeNode) -> int:

		def dfs(root, p, gp):
			if not root: return 0
			if gp and gp.val%2==0:
				return root.val + dfs(root.left,root,p)+dfs(root.right,root,p)
			return 0 + dfs(root.left,root,p)+dfs(root.right,root,p)

		return dfs(root,None,None)
class Solution {
    int sum=0;
    public int sumEvenGrandparent(TreeNode root) {
        dfs(root,null,null);
        return sum;
    }
 void dfs(TreeNode current, TreeNode parent, TreeNode grandParent) {
        if (current == null) return; // base case 
        if (grandParent != null && grandParent.val % 2 == 0) {
            sum += current.val;
        }
				//cur->cur.left ||cur.right , parent=cur,grandPrarent=parent
        dfs(current.left, current, parent)
        dfs(current.right, current, parent);
    }
    }
class Solution {
public:
    void sumGparent(TreeNode* child, int& sum, TreeNode* parent, TreeNode* Gparent){
        if(!child) return;
        if(Gparent) if(Gparent->val % 2 ==0) sum += child->val;
        sumGparent(child->left, sum, child, parent);
        sumGparent(child->right, sum, child, parent);
    }

    int sumEvenGrandparent(TreeNode* root) {
        if(!root) return 0;
        int sum=0;
        sumGparent(root, sum, NULL, NULL); // (child, sum, parent, grand-parent)
        return sum;
    }
};
const dfs = function(node, evenParent) {
    if (!node) return 0;
    
    const isEvenNode = node.val % 2 === 0;
    
    const left = dfs(node.left, isEvenNode);
    const right = dfs(node.right, isEvenNode);
    
    if (!evenParent) return left + right;
    return left + right + (node.left ? node.left.val : 0) + (node.right ? node.right.val : 0);
}

var sumEvenGrandparent = function(root) {
    if (!root) return 0;
    return dfs(root, false);
};
Sum of Nodes with Even-Valued Grandparent