# Sum of Nodes with Even-Valued Grandparent
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-nodes-with-even-valued-grandparent
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/sum-of-nodes-with-even-valued-grandparent/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/sum-of-nodes-with-even-valued-grandparent/image1.jpg) 

**Input:** root = [1]
**Output:** 0

**Constraints:**

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

# Approaches
## Two-Pass Traversal with Parent Mapping
This method uses two passes over the tree. The first pass builds a map to link each node to its parent. The second pass then uses this map to find the grandparent for each node and sums up the values of nodes with an even-valued grandparent.
**Time:** O(N), where N is the number of nodes. The first pass to build the map takes O(N), and the second pass to iterate and sum takes O(N). · **Space:** O(N). The `parentMap` stores N-1 entries. The queue for BFS can also hold up to O(N) nodes in the worst case (for a complete binary tree).
**Pros:** The logic is separated into two distinct and easy-to-understand steps: building parent relationships and then calculating the sum.
**Cons:** Inefficient due to requiring two full passes over the tree's nodes.; Requires O(N) extra space for the parent map, which is generally worse than single-pass solutions that use O(H) space.
### Explanation
This approach first builds a complete map of parent pointers for every node in the tree. This is done by traversing the tree once, for instance, using Breadth-First Search (BFS), and storing `(child, parent)` pairs in a `HashMap`.

After the map is built, we iterate through all nodes that have a parent. For each node, we look up its parent in the map. If a parent exists, we look up the parent's parent (the grandparent). If the grandparent also exists and its value is even, we add the current node's value to our total sum.

While this approach correctly solves the problem, it is suboptimal due to its space and time overhead. It requires O(N) extra space for the map and it traverses all nodes twice.

```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) {
        if (root == null) {
            return 0;
        }

        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        parentMap.put(root, null); // Root has no parent

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parentMap.put(node.left, node);
                queue.offer(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                queue.offer(node.right);
            }
        }
        
        int sum = 0;
        for (TreeNode node : parentMap.keySet()) {
            TreeNode parent = parentMap.get(node);
            if (parent != null) {
                TreeNode grandparent = parentMap.get(parent);
                if (grandparent != null && grandparent.val % 2 == 0) {
                    sum += node.val;
                }
            }
        }
        
        return sum;
    }
}
```
### Algorithm
*   If the `root` is `null`, return 0.
*   Create a `Map<TreeNode, TreeNode>` to store parent pointers.
*   Use a queue for BFS to traverse the tree, starting with the `root`.
*   In the BFS loop, for each `node`, populate the parent map for its children.
*   Initialize `sum = 0`.
*   Iterate through each `node` in the map's key set (which represents all nodes except the root).
*   Get its `parent` from the map.
*   Get the `grandparent` (parent of the parent) from the map.
*   If a `grandparent` exists and its value is even, add the current `node.val` to `sum`.
*   Return `sum`.

## Single-Pass DFS with State Passing
This approach traverses the tree only once using Depth-First Search (DFS). It uses a recursive helper function that keeps track of the current node's parent and grandparent. By passing this information down during the recursion, each node can check its grandparent's value directly.
**Time:** O(N), as each node in the tree is visited exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Efficient in time, as it traverses the tree only once.; More space-efficient than the two-pass approach, especially for balanced trees.
**Cons:** The recursion can lead to a `StackOverflowError` for very deep, skewed trees.; The state (parent, grandparent) needs to be passed through function arguments, making the function signature more complex.
### Explanation
We can solve the problem in a single pass by carrying the necessary context down the tree. A recursive DFS function is a natural fit for this. We define a helper function, `dfs(current, parent, grandparent)`.

The main function starts the process by calling `dfs(root, null, null)`, as the root has no parent or grandparent.

Inside the `dfs` function:
1.  We handle the base case: if `current` is `null`, we stop that path of recursion.
2.  We check if a `grandparent` was passed (i.e., is not `null`) and if its value is even. If so, the `current` node is a grandchild of an even-valued grandparent, and we add its value to a running total.
3.  We then proceed to the next level of the tree by making recursive calls for the children. For the call on `current.left`, the `current` node becomes the new `parent`, and the old `parent` becomes the new `grandparent`. The same logic applies to the call on `current.right`.

This ensures every node is visited once, and the check is performed efficiently using the information passed down the recursion stack.

```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 {
    int sum = 0;

    public int sumEvenGrandparent(TreeNode root) {
        dfs(root, null, null);
        return sum;
    }

    private void dfs(TreeNode current, TreeNode parent, TreeNode grandparent) {
        if (current == null) {
            return;
        }

        if (grandparent != null && grandparent.val % 2 == 0) {
            sum += current.val;
        }

        // The current node becomes the parent, and the parent becomes the grandparent for the next level.
        dfs(current.left, current, parent);
        dfs(current.right, current, parent);
    }
}
```
### Algorithm
*   Initialize a member variable `sum = 0`.
*   Define a recursive function `dfs(node, parent, grandparent)`.
*   Start the process by calling `dfs(root, null, null)`.
*   Inside `dfs`:
    *   If `node` is `null`, return.
    *   If `grandparent` is not `null` and `grandparent.val` is even, add `node.val` to `sum`.
    *   Make a recursive call for the left child: `dfs(node.left, node, parent)`.
    *   Make a recursive call for the right child: `dfs(node.right, node, parent)`.
*   After the initial call completes, return `sum`.

## Optimal Single-Pass Traversal
This is the most efficient approach, performing the calculation in a single pass without explicitly passing parent/grandparent pointers. During the traversal (either DFS or BFS), whenever we encounter a node with an even value, we treat it as a potential grandparent. We then look ahead to its grandchildren and, if they exist, add their values to the total sum.
**Time:** O(N), as each node is visited exactly once. · **Space:** O(H) for recursive DFS (due to the call stack) or O(W) for iterative BFS (due to the queue), where H is the tree height and W is its maximum width. In the worst case, this is O(N).
**Pros:** Most efficient approach with a single pass over the tree.; Simple recursive function signature (`(TreeNode node)`), which is clean and avoids passing extra state.; Can be easily implemented both recursively (DFS) and iteratively (BFS).
**Cons:** The logic inside the traversal function involves several nested `if` checks for grandchildren, which can appear slightly verbose.
### Explanation
This optimal solution traverses the tree once and calculates the sum directly. Instead of a grandchild looking up at its grandparent, we make the grandparent look down at its grandchildren. This simplifies the logic and the state we need to maintain.

We can use any standard traversal, like DFS or BFS. Let's consider a recursive DFS implementation. We define a traversal function that takes a node as input.

Inside the function:
1.  Handle the base case: if the node is `null`, return.
2.  Check if the current `node`'s value is even. If it is, this node is an even-valued grandparent. We then check for the existence of its grandchildren and add their values to our sum.
    *   Check `node.left.left` and `node.left.right`.
    *   Check `node.right.left` and `node.right.right`.
3.  Crucially, regardless of the current node's value, we must continue the traversal to its children (`node.left` and `node.right`) because there might be other even-valued grandparents deeper in the tree.

This method is efficient because each node is visited once, and for each node, we only perform a few constant-time checks on its immediate children and grandchildren.

```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) {
        if (root == null) return 0;
        
        int sum = 0;
        // Check if the current node is an even-valued grandparent
        if (root.val % 2 == 0) {
            if (root.left != null) {
                if (root.left.left != null) sum += root.left.left.val;
                if (root.left.right != null) sum += root.left.right.val;
            }
            if (root.right != null) {
                if (root.right.left != null) sum += root.right.left.val;
                if (root.right.right != null) sum += root.right.right.val;
            }
        }
        
        // Recursively call for children and add their results
        sum += sumEvenGrandparent(root.left);
        sum += sumEvenGrandparent(root.right);
        
        return sum;
    }
}
```
### Algorithm
*   This can be implemented with either DFS or BFS.
*   **DFS (Recursive) Algorithm:**
    *   Base Case: If the current `node` is `null`, return 0.
    *   Initialize a local `sum = 0`.
    *   If `node.val` is even:
        *   Check for the four possible grandchildren. If a grandchild exists, add its value to `sum`.
    *   Recursively call the function for the left child and add the result to `sum`.
    *   Recursively call the function for the right child and add the result to `sum`.
    *   Return the total `sum`.
*   **BFS (Iterative) Algorithm:**
    *   Initialize `sum = 0` and a `Queue` with the `root`.
    *   While the queue is not empty:
        *   Dequeue a `node`.
        *   If `node.val` is even, check for its grandchildren and add their values to `sum`.
        *   Enqueue the node's non-null children.

# Solutions
### Java

```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 { private int res ; public int sumEvenGrandparent ( TreeNode root ) { res = 0 ; dfs ( root , root . left ); dfs ( root , root . right ); return res ; } private void dfs ( TreeNode g , TreeNode p ) { if ( p == null ) { return ; } if ( g . val % 2 == 0 ) { if ( p . left != null ) { res += p . left . val ; } if ( p . right != null ) { res += p . right . val ; } } dfs ( p , p . left ); dfs ( p , p . right ); } }
```

### CPP

```cpp
/** * 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 res ; int sumEvenGrandparent ( TreeNode * root ) { res = 0 ; dfs ( root , root -> left ); dfs ( root , root -> right ); return res ; } void dfs ( TreeNode * g , TreeNode * p ) { if ( ! p ) return ; if ( g -> val % 2 == 0 ) { if ( p -> left ) res += p -> left -> val ; if ( p -> right ) res += p -> right -> val ; } dfs ( p , p -> left ); dfs ( p , p -> right ); } };
```

### Python

```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 : self . res = 0 def dfs ( g , p ): if p is None : return if g . val % 2 == 0 : if p . left : self . res += p . left . val if p . right : self . res += p . right . val dfs ( p , p . left ) dfs ( p , p . right ) dfs ( root , root . left ) dfs ( root , root . right ) return self . res
```