Sum of Nodes with Even-Valued Grandparent

Medium
1945.

Sum of Nodes with Even-Valued Grandparent

Sum of Nodes with Even-Valued Grandparent is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Salesforce interviews.

Given the root of a binary tree, return the sum of the values of every node whose grandparent (the parent of its parent) has an even value. If no node has an even-valued grandparent, return 0.

Example 1

Input
root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output
18
Explanation
6 is even, so its grandchildren 2, 7, 1 and 3 count; 8 is even, so its grandchild 5 counts (the even 2 has no grandchildren). Total 2 + 7 + 1 + 3 + 5 = 18.

Example 2

Input
root = [1]
Output
0
Explanation
A single node has no grandparent.

Example 3

Input
root = [2,4,6,8,10,12,14]
Output
44
Explanation
The even root's four grandchildren add up to 8 + 10 + 12 + 14 = 44.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumEvenGrandparent = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of Nodes with Even-Valued Grandparent — Solution

Sum of Nodes with Even-Valued Grandparent solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Sum of Nodes with Even-Valued Grandparent is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Salesforce interviews.

Problem statement

Given the root of a binary tree, return the sum of the values of every node whose grandparent (the parent of its parent) has an even value. If no node has an even-valued grandparent, return 0.

Example 1

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: 6 is even, so its grandchildren 2, 7, 1 and 3 count; 8 is even, so its grandchild 5 counts (the even 2 has no grandchildren). Total 2 + 7 + 1 + 3 + 5 = 18.

Example 2

Input: root = [1]
Output: 0
Explanation: A single node has no grandparent.

Example 3

Input: root = [2,4,6,8,10,12,14]
Output: 44
Explanation: The even root's four grandchildren add up to 8 + 10 + 12 + 14 = 44.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 100

Hints for Sum of Nodes with Even-Valued Grandparent

  1. Hint 1

    A node only needs to know two values from above it: its parent's and its grandparent's.

  2. Hint 2

    Walk down the tree passing those two values along; a child's grandparent is the current node's parent.

  3. Hint 3

    Start the root with a parent and grandparent value that is odd (say 1), so nothing is counted for the top two levels by mistake.

How to solve Sum of Nodes with Even-Valued Grandparent

During a depth-first walk, pass each node its parent's and grandparent's values; add the node when the grandparent's value is even.

Approach

  1. Call walk(root, parent = 1, grandparent = 1) — 1 is odd, standing for "no ancestor".
  2. At a node, start with its own value if grandparent is even, else 0.
  3. Add walk(child, node.val, parent) for both children and return the total.

Why it works

Moving one level down shifts the window: the child's parent is the current node and its grandparent is the current node's parent. Every node is visited once and tested against exactly its own grandparent.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Checking the parent's parity instead of the grandparent's.
  • Using 0 as the "missing" value — 0 is even and would count the root's children.

Reference solution

Python

from typing import Optional

def sumEvenGrandparent(root: Optional[TreeNode]) -> int:
    def walk(node, parent, grand):
        if node is None:
            return 0
        total = node.val if grand % 2 == 0 else 0
        return total + walk(node.left, node.val, parent) + walk(node.right, node.val, parent)

    return walk(root, 1, 1)

Java

public static int sumEvenGrandparent(TreeNode root) {
    return grandWalk(root, 1, 1);
}

static int grandWalk(TreeNode node, int parent, int grand) {
    if (node == null) return 0;
    int total = grand % 2 == 0 ? node.val : 0;
    return total + grandWalk(node.left, node.val, parent) + grandWalk(node.right, node.val, parent);
}

C++

int grandWalk(TreeNode* node, int parent, int grand);

int sumEvenGrandparent(TreeNode* root) {
    return grandWalk(root, 1, 1);
}

int grandWalk(TreeNode* node, int parent, int grand) {
    if (!node) return 0;
    int total = grand % 2 == 0 ? node->val : 0;
    return total + grandWalk(node->left, node->val, parent) + grandWalk(node->right, node->val, parent);
}

JavaScript

var sumEvenGrandparent = function(root) {
    return grandWalk(root, 1, 1);
};

var grandWalk = function(node, parent, grand) {
    if (node === null) return 0;
    var total = grand % 2 === 0 ? node.val : 0;
    return total + grandWalk(node.left, node.val, parent) + grandWalk(node.right, node.val, parent);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)