loading...
Cover image for Algorithms Problem Solving: Sum of nodes

Algorithms Problem Solving: Sum of nodes

teekay profile image TK Originally published at leandrotk.github.io ・4 min read

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

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

Algorithms Problem Solving Series (23 Part Series)

1) Algorithms Problem Solving: Jewels and Stones 2) Algorithms Problem Solving: Ransom Note 3 ... 21 3) Algorithms Problem Solving: Sum of nodes 4) Algorithms Problem Solving: Subtract product and sum 5) Algorithms Problem Solving: Cloned Binary Tree 6) Algorithms Problem Solving: Group the people 7) Algorithms Problem Solving: Equal Reversed Arrays 8) Algorithms Problem Solving: Even Number of Digits 9) Algorithms Problem Solving: Reduce to zero 10) Algorithms Problem Solving: Deepest Leaves Sum 11) Algorithms Problem Solving: Tree to greater sum 12) Algorithms Problem Solving: to Lower case 13) Algorithms Problem Solving: Balanced Strings 14) Algorithms Problem Solving: Number of students 15) Algorithms Problem Solving: Destination City 16) Algorithms Problem Solving: Maximum 69 Number 17) Algorithms Problem Solving: Shuffle the array 18) Algorithms Problem Solving: Insert into Binary Search Tree 19) Algorithms Problem Solving: Construct Binary Search Tree from Preorder Traversal 20) Algorithms Problem Solving: Odd in Matrix 21) Algorithms Problem Solving: Sort the Matrix Diagonally 22) Algorithms Problem Solving: Discount for prices 23) Algorithms Problem Solving: Running Array Sum

Posted on May 31 by:

teekay profile

TK

@teekay

Sharing knowledge https://leandrotk.github.io/tk

Discussion

markdown guide