In the quest to improve to improve my algorithmic thinking and problem solving abilities, I've been doing many problems from various online resources. These posts will be a space for me to explain the thinking behind a solution (but possibly not the most optimal one).

As I've been brushing up on my data structures, there is one data structure that scares me if it was ever one asked during a technical interview. That would be graphs. Not because I don't understand them, but the algorithms behind them take me longer to think about and put into practice. Trees on the other hand always seem way easy to me, probably because there's not always as much of a need to hold onto values. This post is, thankfully about trees and not graphs.

The problem in question this time is called Sum of Nodes with Even-Valued Grandparent. You can go to the LeetCode page to learn more about it, but in summary the name pretty much explains itself. The only extra thing to consider is that if there are no even-numbered grandparents you should return 0 (which...makes sense).

Almost immediately when I read the problem I had ideas in my head. Do I want to use recursion? Breadth-first search? Depth-first search? Is this problem actually as easy as it sounds? (Side note: one weird feeling I get when doing problems on HackerRank and LeetCode is the difficulties don't always seem to be calibrated correctly. I've done many Medium problems that are pretty easy, and a couple Easy problems that may be on the edge of medium. Is it due to my knowledge or improper design? Who knows)

While I don't hate recursion (it's super useful a lot of the time), I wanted to go a non recursive route for this problem because other than the graph issue I mentioned above, dynamic programming (DP) is another topic I need practice on. While doing this problem with out recursion isn't exactly DP, I still wanted to be in a similar mindset.

After picking that method I also decided to try solving this using breath-first search (BST). While BST is usually used when looking for a shortest route or the like, that just came first in my head so I went with it. Once I solved it, I actually looked at other solutions and basically everyone else used depth-first search (DFS)! I guess I like being unique. (DFS is usually the pick when you want to 'touch' every node of a tree, but you technically don't need to go to every node so...)

Finally to the actual solution! To start off I double checked the constraints to make sure I didn't need to worry about being given an empty tree, always something you should look at because you don't want to stupidly fail test cases because you didn't think of the edge cases. After that I set up some initial variables, result to keep track of the sum, and because I went with a BST also a queue (in Python remember to import the collections module to use the deque function/data type:

result = 0
queue = collections.deque()

Next I got the queue and loop set up, which means adding the current root to it and having the loop continue while there are elements in the queue. Also some additional variables to make it easier to keep track of if a node has a left and/or right child (Note: my current build of this website makes tabs and multiple spaces tricky...something I need to work on :/):

queue.append(root)
while queue:
 leftNode = False
 rightNode = False

Next I made sure that we grab the next element of the queue and check to see if it has children to add onto the queue, then also update the variables above (to save space, I just include the left child here, the right would be almost identical):

currNode = queue.popleft()
if currNode.left and (currNode.left.left or currNode.left.right):
queue.append(currNode.left)
leftNode = True

You'll notice that the if statement also checks if the left child itself has children and wonder a) why and b) wouldn't that be a problem if the left child doesn't even exist!? Well, for anyone who is new to Python, it uses short-circuit operators, so if currNode.left returned False, then the and would have to be false so it doesn't even check the right side. I also checked the grandchildren here because there is no need to add a node to the queue if it doesn't have any grandchildren due to the expectation of the problem.

Next, a simple line of code to ensure we are only doing more work (calculating the results) if the node we are at (a grandparent) is an even value:

if currNode.val % 2 == 0:

Then finally, a set of nested ifs to make sure each child exists, has grandchildren, and if so add that grandchild's value to the result (again, just adding the left child code here):

if leftNode:
if currNode.left.left:
result += currNode.left.left.val
if currNode.left.right:
result += currNode.left.right.val

And don't forget this important line!

return result

With all that put together, here is the final solution:

import collections

class Solution:
def sumEvenGrandparent(self, root: TreeNode) -> int:
result = 0
queue = collections.deque()
queue.append(root)
while queue:
leftNode = False
rightNode = False
currNode = queue.popleft()
if currNode.left and (currNode.left.left or currNode.left.right):
queue.append(currNode.left)
leftNode = True
if currNode.right and (currNode.right.left or currNode.right.right):
queue.append(currNode.right)
rightNode = True
if currNode.val % 2 == 0:
if leftNode:
if currNode.left.left:
result += currNode.left.left.val
if currNode.left.right:
result += currNode.left.right.val
if rightNode:
if currNode.right.left:
result += currNode.right.left.val
if currNode.right.right:
result += currNode.right.right.val
return result

And that is how I went about thinking through this problem! My solutions aren't always the most perfect solutions, and sometimes I admit that I need to look at the hints and/or discussions, but once you get that 'ah-ha' moment it's a thrill and code code starts to flow.

If you have any suggestions for how I could have improved this solution, feel free to drop me a line using the links in the footer.