Algorithms Problem Solving: Sum of nodes
Tags: algorithms, python, computerscience, interview
Published: 2020-05-31 11:51:34

---
title: Algorithms Problem Solving: Sum of nodes
published: true
description: Solving algorithms problems with TK
tags: algorithms, python, computerscience, interview
cover_image: https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/trees-in-smoke.jpg
canonical_url: https://leandrotk.github.io/tk/series/algorithms-problem-solving/sum-of-nodes.html
series: Algorithms Problem Solving Series
---

This post is part of the [Algorithms Problem Solving](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html) series.

## Problem Description

This is the *[Sum of Nodes with Even-Valued Grandparent](https://leetcode.com/problems/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:

![](https://raw.githubusercontent.com/leandrotk/tk/master/series/algorithms-problem-solving/assets/tree-example.png)

## 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.

```python
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.

```python
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:

```python
if node.left:
    left += sum_even_grandparent(node.left)
```

I needed to also do the same code to the right child:

```python
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:

```python
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:

```python
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](https://leandrotk.github.io/tk/2017/09/learning-python-from-zero-to-hero/index.html)
- [Algorithms Problem Solving Series](https://leandrotk.github.io/tk/series/algorithms-problem-solving/index.html)
- [Big-O Notation For Coding Interviews and Beyond](https://www.educative.io/courses/big-o-notation-for-interviews-and-beyond?aff=x8bV)
- [Learn Python from Scratch](https://www.educative.io/courses/learn-python-from-scratch?aff=x8bV)
- [Learn Object-Oriented Programming in Python](https://www.educative.io/courses/learn-object-oriented-programming-in-python?aff=x8bV)
- [Data Structures in Python: An Interview Refresher](https://www.educative.io/courses/data-structures-in-python-an-interview-refresher?aff=x8bV)
- [Data Structures and Algorithms in Python](https://www.educative.io/courses/ds-and-algorithms-in-python?aff=x8bV)
- [Data Structures for Coding Interviews in Python](https://www.educative.io/courses/data-structures-coding-interviews-python?aff=x8bV)
- [One Month Python Course](https://mbsy.co/lG6tv)