Problem 1315

Abstract / Summary

Sum the values of all nodes whose grandparents have even values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1315.py

class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        result = 0

        def deeper(node, parent, grandparent):
            if node:
                if grandparent % 2 == 0:
                    nonlocal result
                    result += node.val

                deeper(node.left,  node.val, parent)
                deeper(node.right, node.val, parent)

        deeper(root, -1, -1)
        return result
15 lines | 451 bytes | submitted October 29, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 86% (200k+ submissions).

Typical patterns to solve this problem:
  • Binary Tree
  • Breadth First Search
  • Depth First Search
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a method sumEvenGrandparent that computes the sum of all node values in a binary tree whose grandparent node holds an even integer. The algorithm relies on a depth-first traversal implemented via a nested helper function. By passing the current node together with its parent and grandparent values, the code can decide at each step whether the node contributes to the final total.

Key Steps

The method begins by creating a mutable accumulator named result and initializing it to zero. This variable will hold the cumulative sum as the recursion proceeds.

result = 0

A nested function called deeper is declared. It accepts three parameters: the current node, the value of its parent, and the value of its grandparent. The function is defined inside sumEvenGrandparent so that it can capture the result variable from the enclosing scope.

def deeper(node, parent, grandparent):

Inside deeper, the first operation checks whether the supplied node reference is non-null. This guard prevents attempts to access attributes of a missing child and naturally terminates the recursion at leaf boundaries.

if node:

When a valid node is present, the code evaluates whether the grandparent value is even. The modulo operator determines parity, and the condition is satisfied only when the remainder of division by two equals zero. If the condition holds, the nonlocal declaration grants write access to the outer result variable, and the node’s value is added to the accumulator.

if grandparent % 2 == 0:
    nonlocal result
    result += node.val

The recursion proceeds by invoking deeper for the left and right children of the current node. The arguments shift forward: the current node’s value becomes the new parent, and the previous parent value becomes the new grandparent. This sliding window of three consecutive generations enables the algorithm to evaluate the even-grandparent condition at every depth without storing the entire ancestry path.

deeper(node.left,  node.val, parent)
deeper(node.right, node.val, parent)

After defining deeper, the initial call supplies the root of the tree along with sentinel values -1 for both parent and grandparent. The sentinel values are deliberately odd, ensuring that the root and its immediate children are never mistakenly counted as having an even grandparent.

deeper(root, -1, -1)

Finally, the method returns the accumulated sum.

return result

Edge Cases

The implementation gracefully handles an empty tree because the initial call to deeper receives root as None. The guard if node: immediately fails, and no further recursion occurs, leaving result at its initial zero value.

When the tree consists of a single node, the same guard prevents any addition to result because the grandparent value remains the sentinel -1, which is odd. Consequently, the method returns zero, reflecting the absence of a qualifying grandparent.

The use of sentinel values -1 for both parent and grandparent also covers the scenario where the root’s children are processed. Since -1 is odd, the condition grandparent % 2 == 0 evaluates to false, ensuring that nodes lacking a true grandparent are never counted.

If a node’s value itself is negative or zero, the parity check still functions correctly because the modulo operation works uniformly for all integers. The accumulator correctly adds negative values when the grandparent is even, allowing the sum to reflect the exact arithmetic result of the qualifying nodes.

Performance Optimizations

The algorithm avoids auxiliary data structures such as stacks or explicit path lists. By passing only scalar values for parent and grandparent, each recursive call consumes a minimal amount of memory on the call stack, and no heap allocation occurs beyond the inherent recursion frames.

The early if node: guard eliminates unnecessary work for null children, preventing the function from descending into non-existent subtrees. This short-circuiting reduces the number of recursive invocations, especially in highly unbalanced trees where many leaf nodes have only one child.

Using the nonlocal keyword to update result eliminates the need to propagate partial sums back up the call chain. Each recursive frame directly contributes to the shared accumulator, which avoids the overhead of returning intermediate values and merging them at each level.

The parity test grandparent % 2 == 0 is a constant-time arithmetic operation, and it is performed only when a node exists. By placing the test inside the if node: block, the code ensures that the modulo operation is never executed for null references, preserving efficiency.

Overall, the design leverages a tight recursive pattern with minimal parameter passing and in-place accumulation, resulting in a solution that scales naturally with the size of the input tree while keeping runtime overhead low.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a tree made of numbers where every number can have children branching off below it. This computer program acts like a tiny explorer visiting every single member of this tree family. It keeps a secret notebook to remember two generations of ancestors for every person it visits.

When the explorer reaches someone new, it looks at the grandparent of that person. If that grandparent is wearing an even number, like two or four or six, the explorer grabs the value of the new person and adds it to a big pile it is collecting. After looking at the grandparent, the explorer moves down one step to the left child and then over to the right child. It keeps doing this dance over and over again until it has checked every single person living in the tree. Once every branch has been peeked at, the big pile of values collected from the children of even-numbered grandparents is complete.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.26 | σ = 1.20

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
28 links | 18 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 solutions   October 29, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality