Sum of Nodes with Even Grandparent Values

Given a binary tree root, return the sum of all node values whose grandparents have an even value.

Constraints

• 0 ≤ n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Sum-of-Nodes-with-Even-Grandparent-Values

Examples

Example 1

Input

• root =

Output

• answer = 15

Explanation

Nodes 6, 7, and 2 have an even value grandparent.

Solution