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.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Salesforce
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^41 <= Node.val <= 100
Hints for Sum of Nodes with Even-Valued Grandparent
Hint 1
A node only needs to know two values from above it: its parent's and its grandparent's.
Hint 2
Walk down the tree passing those two values along; a child's grandparent is the current node's parent.
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
- Call
walk(root, parent = 1, grandparent = 1)— 1 is odd, standing for "no ancestor". - At a node, start with its own value if
grandparentis even, else 0. - 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)