This post is part of the Algorithms Problem Solving series.
Problem Description
This is the Sum of Nodes with Even-Valued Grandparent problem. The description looks like this:
Given a binary tree, return the sum of values of nodes with even-valued grandparent (A grandparent of a node is the parent of its parent, if it exists.).
If there are no nodes with an even-valued grandparent, return 0.
Examples
[6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]
=> 18
The tree representation looks like this:
Solution
To come with a solution, I drafted some rules that I needed to implement in the algorithm:
- I need to traverse the tree
- The node needs to have a grandparent with an even value
To traverse a tree is straightfoward. I just need to verify if it has a (left | right) child and make a recursive call passing the expected child.
The second rule is a bit tricky. To add the node's value, I need to verify its grandparent, but I don't have access to the grandparent node. I could do in reverse in this case. Get the grandchildren's value if the current node has an even value.
To do this logic I need to verify if the current node has a child and a grandchild before trying to access a possible grandchild. I tried this idea in the left node first.
if root.left and root.left.left and root.val % 2 == 0:
root.left.left.val
With that, I have access to the grandparent node and I can get the grandchild's value.
Now that I can get the grandchild's value, I need to store it in a variable. So I initialized a variable left with value 0 to get the sum of all left part of the tree. I needed to do the left child's left child and the left child's right child. So basically the left and the right grandchildren.
def sum_even_grandparent(node):
left = 0
if node.left and node.left.left and node.val % 2 == 0:
left += node.left.left.val
if node.left and node.left.right and node.val % 2 == 0:
left += node.left.right.val
At the same time I needed to do the same implementation for left child:
if node.left:
left += sum_even_grandparent(node.left)
I needed to also do the same code to the right child:
right = 0
if node.right and node.right.left and node.val % 2 == 0:
right += node.right.left.val
if node.right and node.right.right and node.val % 2 == 0:
right += node.right.right.val
if node.right:
right += sum_even_grandparent(node.right)
The idea here is to verify all current node's grandchildren and sum the values if they follow the rule.
As we do a recursive call, it will traverse the entire tree.
After traverse the left and the right parts of the tree, we just need to get the sum of the left part of the tree and the right part of the tree.
And then just return the sum of both.
The entire implementation looks like this:
def sum_even_grandparent(node):
left = 0
right = 0
if node.left and node.left.left and node.val % 2 == 0:
left += node.left.left.val
if node.left and node.left.right and node.val % 2 == 0:
left += node.left.right.val
if node.left:
left += sum_even_grandparent(node.left)
if node.right and node.right.left and node.val % 2 == 0:
right += node.right.left.val
if node.right and node.right.right and node.val % 2 == 0:
right += node.right.right.val
if node.right:
right += sum_even_grandparent(node.right)
return right + left
Another solution is to pass the grandparent down the tree. We can build a helper function to pass these information:
def sum_even_grandparent(node):
return helper(node, 1, 1)
def helper(node, parent, grandparent):
if node is None:
return 0
return helper(node.left, node.val, parent) \
+ helper(node.right, node.val, parent) \
+ (node.val if grandparent % 2 == 0 else 0)
The first helper call within the helper function is for the left side of the tree. The second is for the right side. As we pass the grandparent now, we just need to verify if it is an even value. It returns the node value if it is even. Zero if it is not.
Resources
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Big-O Notation For Coding Interviews and Beyond
- Learn Python from Scratch
- Learn Object-Oriented Programming in Python
- Data Structures in Python: An Interview Refresher
- Data Structures and Algorithms in Python
- Data Structures for Coding Interviews in Python
- One Month Python Course
Top comments (0)