This is our solution and implementation to problem #1315: Sum of Nodes with Even-Valued Grandparent on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Sum of Nodes with Even-Valued Grandparent on LeetCode.
Problem Analysis
We need to collect a sum of value of nodes throught the input tree, but we can only include a node's value if it's grandparent's value is even. In the TreeNode class provided by the problem, there is no reference to the parent node, so we will not be able to traverse up two levels at each point to check if the grandparent's value is even. We'll need to find a way to check these values without traversing the tree more than once, as such an algorithm would be very inefficient. We cannot filter any subtrees entirely, because the value of any given node does not predict if its children or grandchildren will be even or odd, so we cannot infer anything useful about these subtrees.
Implementation Strategy
Based on the contraints of the problem, we will implement a recursive depth first search method which takes in additional values of the parent's value and grandparent's value. We'll provide initial values of -1 for the beginning of the traversal, as the root doesn't have any parent or grandparent nodes. Then, for each level of iteration, check if the grandparent's value is even, and if it is, include the current node's value in the sum. Then, recursively call the method for the left and right child nodes, if they are not null.
Space and Time Complexity
The average space complexity is O(log n), as the function call stack will need to record one entry per level of depth within the traversal. In the worst case, where each node in the binary tree only has a left node, or only a right node, throughout, the structure will behave as a linked list and will have a worst space complexity of O(n). The time complexity is O(n), as we will be visiting every node exactly one time.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.