The blog for Design Patterns, Linux, HA and Myself!

Sum of Nodes With Even Valued Grandparent Solution

Leetcode Solution: Understand Leetcode problem Sum of Nodes With Even Valued Grandparent(1315) Solution

In this article we’ll be solving the problem: Sum of Nodes with Even-Valued Grandparent. Just like the problem, Deepest Leaves Sum and Leaf Similar Trees, this problem also requires a change in the simple pre order Tree Traversal.

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.

Example 1:
               /     \ 
              7       8
             / \     / \
            2   7   1   3
           /   / \       \
          9   1   4       5
    Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
    Output: 18
    Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the
    even-value grandparents.


    The number of nodes in the tree is between 1 and 10^4.
    The value of nodes is between 1 and 100.


To solve this problem we’ve to find the sum of all the nodes whose grand parents have even values. Now, in the simple pre order tree traversal, the node does not have the access to its parent or grand parents, so, we’ll have to update the pre order tree traversal by passing the parent and the grand parents in the tree traversal recursions. Here is the program for a simple pre order tree traversal:

func preOrder(node *TreeNode) {
    if node == nil {
        return nil

The node variable cannot access its parent here. But if we pass the parent, and the grand parent in the pre order function then the node can access them, for example:

func preOrder(node, parent, grandParent *TreeNode) {
    if node == nil {
        return nil
    if parent != nil {
        // in case of root parent will be nil
    if grandParent != nil {
        // for the direct children of root the grandParent will be nil
    // for node's left and the right child the node's parent become the grand parent
    preOrder(node.Left, node, parent)
    preOrder(node.Right, node, parent)

Here, we’re passing the parent and the grand parent to the preOrder function and this way it is becoming available for each of the nodes.

As we’ve looked into how to access the grand parent for a node we can then proceed to solve the current problem.

Tree Traversal Approach

In this(^) image the color for the nodes match with their grand parent. The nodes in red will be ignored as the grand parent has an odd value.

Here is the program for that:

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode

func sumEvenGrandparent(root *TreeNode) int {
    var sum int
    if root == nil {
        return 0
    sum = 0
    preOrder(root, nil, nil, &sum)
    return sum

func preOrder(node, parent, grandParent *TreeNode, sum *int) {
    if grandParent != nil && grandParent.Val % 2 == 0 {
        *sum += node.Val
    if node.Left != nil {
        preOrder(node.Left, node, parent, sum)
    if node.Right != nil {
        preOrder(node.Right, node, parent, sum)

The logic remains same to what we’ve discussed earlier. The new portion in program code is a check to find if the grand parent has an even value. This program can be found on GitHub as well.

Loading Comments... Disqus Loader
comments powered by Disqus