Algorithms Problem Solving: Sum of nodes

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.

Algorithms Problem Solving: Sum of nodes

Problem Description

Examples

Solution

Resources