Even Grandparent Sum in a Binary Tree

You are given a binary tree. Your task is to compute the sum of all node values that have an even-valued grandparent.

A node's grandparent is defined as the parent of its parent (if it exists). Mathematically, if we denote by \(S\) the desired sum and by \(v.val\) the value of a node \(v\), then:

\(S = \sum_{\substack{v \in T \\ (\text{grandparent}(v)\,\%\,2 = 0)}} v.val\)

Note that if a node does not have a grandparent or its grandparent's value is odd, then it will not contribute to the sum.

inputFormat

The input consists of a single line representing the binary tree in level-order (breadth-first) traversal, where each value is separated by a space. Use the string "null" to represent a missing node.

outputFormat

Output a single integer representing the sum of all node values in the tree that have an even-valued grandparent.## sample

6 7 8 2 7 1 3 9 null 1 4 null null null 5

18