Sum of Nodes with Even-Valued Grandparent

Given a binary tree rooted at root, return the sum of values of nodes that have an even-valued grandparent. A grandparent of a node is the parent of its parent, if it exists.

This is LeetCode 1315: Sum of Nodes with Even-Valued Grandparent.

For example, given the tree [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5], the even-valued grandparents are nodes 6 and 8. Node 6's grandchildren are 2, 7, 1, and 3. Node 8's only grandchild is 5. The sum is 2 + 7 + 1 + 3 + 5 = 18.

Why this problem matters

This problem teaches you a pattern that comes up often in tree problems: passing ancestor information down through recursion. Many tree questions ask you to make decisions based on a node's parent or grandparent, not just the node itself. Once you learn to thread that context through your DFS calls, a whole family of problems becomes easy.

It also reinforces the idea that tree DFS is just a framework. The interesting part is deciding what state to carry along as you recurse. Here, you carry the parent and grandparent values. In other problems, you might carry a running sum, a path, or a depth counter. The DFS skeleton stays the same.

The key insight

At each node, you need to know whether its grandparent has an even value. You do not need to look upward in the tree. Instead, pass the parent and grandparent values downward as parameters during DFS. When you visit a node, if its grandparent value is even, add the current node's value to the result. Then recurse into children, shifting the ancestor chain: the current parent becomes the new grandparent, and the current node becomes the new parent.

The solution

def sum_even_grandparent(root):
    def dfs(node, parent, grandparent):
        if not node:
            return 0
        total = node.val if grandparent % 2 == 0 else 0
        total += dfs(node.left, node.val, parent)
        total += dfs(node.right, node.val, parent)
        return total

    return dfs(root, 1, 1)

The function dfs takes three arguments: the current node, the parent's value, and the grandparent's value. At each node, it checks whether the grandparent is even. If so, it adds the current node's value. Then it recurses into both children, shifting the ancestor chain forward: the current node's value becomes the new parent, and the old parent becomes the new grandparent.

We initialize with parent=1 and grandparent=1 because the root has no real parent or grandparent. Using 1 (an odd value) ensures the root and its children are never incorrectly counted as having an even-valued grandparent.

Visual walkthrough

The DFS visits every node exactly once, threading the parent and grandparent values through the recursion. Nodes 6 and 8 are even-valued grandparents. Node 2 is also even but its only child (9) has no children, so 2 contributes nothing as a grandparent. The five grandchildren of even nodes sum to 18.

Complexity analysis

We visit each of the n nodes exactly once, doing O(1) work at each node. The space comes from the recursion stack, which goes as deep as the tree height h. In the worst case (a skewed tree), h = n. For a balanced tree, h = log n.

The building blocks

1. DFS with ancestor state

def dfs(node, parent, grandparent):
    if not node:
        return 0
    result = process(node, parent, grandparent)
    result += dfs(node.left, node.val, parent)
    result += dfs(node.right, node.val, parent)
    return result

This pattern works for any problem where you need to know about a node's ancestors. You carry the ancestor values as parameters and shift them forward at each recursive call. You can extend it to track more ancestors by adding more parameters.

2. Sentinel values for missing ancestors

dfs(root, 1, 1)

When the root has no real parent or grandparent, you need safe default values. Pick values that will not trigger the condition you are checking. Since we check for even grandparents, we use 1 (odd) so the root and its children are not falsely counted.

Edge cases

• Single node: The root has no grandparent, so the answer is 0 regardless of the root's value.
• Two levels only: No node has a grandparent. The answer is always 0.
• All even values: Every node at depth 2 or greater gets counted, since every grandparent is even.
• No even values in tree: The sum is 0 because there are no even-valued grandparents.
• Skewed tree (linked list shape): Each node has at most one grandparent. The DFS still works correctly because it only tracks the two nearest ancestors.

From understanding to recall

You just walked through a DFS that passes ancestor values as parameters and checks a condition at each node. The solution is compact: a single recursive function with two extra parameters. It makes sense right now. But will you remember to initialize the parent and grandparent to odd sentinel values? Will you remember to shift the ancestor chain correctly at each recursive call?

Understanding a solution once is not the same as producing it under pressure. Spaced repetition bridges that gap. You practice writing the ancestor-tracking DFS from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the parameter-passing pattern until it becomes automatic.

Passing ancestor context through DFS is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Maximum Path Sum - Another tree DFS problem
• Diameter of Binary Tree - Tracking values through tree traversal
• Path Sum III - DFS with ancestor context

CodeBricks helps you internalize tree traversal patterns so they become automatic. Instead of re-deriving the ancestor-tracking approach from scratch every time, you build muscle memory through targeted repetition. The DFS-with-parameters pattern gets its own drill, so you can practice it independently and combine it when problems like this come up.