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
Difficulty
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
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Solved On The Same Day
- problem 1227: Airplane Seat Assignment Probability
- problem 1325: Delete Leaves With a Given Value
- problem 1333: Filter Restaurants by Vegan-Friendly, Price and Distance
- problem 1344: Angle Between Hands of a Clock
- problem 1220: Count Vowels Permutation
Extra
- 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