Sum of Nodes with Even-Valued Grandparent — Solution

Problem

Given a binary tree, find the sum of all node values whose grandparent (the parent's parent) has an even value. Nodes with no grandparent — meaning the root and its direct children — are excluded entirely.

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

• Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
• Output: 18
• Explanation: Nodes 2, 7, 1, 3, and 5 qualify — their grandparents are 6, 6, 6, 6, and 8 (all even) — summing to 18.

Intuition

To check whether a node qualifies, you need to look two levels up, not at the node itself. Rather than storing parent pointers or traversing upward, pass the parent and grandparent values downward as parameters. By the time recursion reaches any node, both ancestor values are already in hand — so the check is instant and the tree only needs one pass.

Solution — DFS with Grandparent Tracking

Carry the current node's parent and grandparent values forward through a recursive DFS. At each node, if the grandparent value is even, add the node's value to the running sum.

1. Start DFS from the root, initializing both parent and grandparent to 1 — an odd sentinel so root's children are not incorrectly counted.
2. At each node, if the grandparent value is even, include this node's value.
3. Recurse into the left child, passing the current node's value as the new parent and the old parent as the new grandparent.
4. Recurse into the right child with the same updated parent/grandparent pair.
5. Return the accumulated sum back up the call stack.

1from typing import Optional
2
3class Solution:
4    def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
5        def dfs(node: Optional[TreeNode], parent_value: int, grandparent_value: int) -> int:
6            if not node:
7                return 0
8            # include this node only when its grandparent is even
9            current = node.val if grandparent_value % 2 == 0 else 0
10            left_sum = dfs(node.left, node.val, parent_value)
11            right_sum = dfs(node.right, node.val, parent_value)
12            return current + left_sum + right_sum
13
14        return dfs(root, 1, 1)  # odd sentinels: neither triggers an even-grandparent match

Time: O(n) — every node is visited exactly once.

Space: O(h) — the recursion stack reaches the height of the tree; O(log n) for a balanced tree and O(n) worst case for a completely skewed tree.

Complexity Summary

Common Mistakes

• Swapping parent and grandparent in the recursive call — the current node becomes the new parent and the old parent becomes the new grandparent; reversing this order produces wrong results on every level below.
• Using 0 as the sentinel for "no grandparent" — 0 is even, so root's direct children would be incorrectly counted; any odd value (1, -1 in Python) is a safe sentinel.
• Checking the parent's value instead of the grandparent's — the problem says grandparent, two levels up, not one.
• Using -1 % 2 in C++ or Java — in C++ and Java, -1 % 2 evaluates to -1, not 1; using 1 as the sentinel avoids this language-specific pitfall entirely.
• Accidentally passing node.val as both parent and grandparent — the grandparent argument must receive the old parent value, not the current node's value.

Related Problems

• Binary Tree Level Order Traversal — BFS traversal that similarly requires attaching level context to each node as it is processed
• Path Sum III — passes a running prefix sum down the tree to test path conditions without traversing back up
• Sum Root to Leaf Numbers — accumulates a running number through each recursive call and finalizes it only at leaves
• Binary Tree Zigzag Level Order Traversal — level-order traversal where a directional flag is threaded forward alongside each level
• Maximum Depth of Binary Tree — foundational DFS pattern where a depth counter is passed down as a parameter