Sum of Nodes with Even-Valued Grandparent solution and explanation
9 more videos on this problem
1315. Sum of Nodes with Even-Valued Grandparent | BINARY TREE | LEETCODE MEDIUM | CODE EXPLAINERcode Explainer · 6:48 · 3K views
Sum of Nodes with Even-Valued Grandparent (Leetcode 1315)Coding Interviews · 11:15 · 1K views
LeetCode 315 | Sum of Nodes with Even-Valued Grandparent | Solution Explained (Java + Whiteboard)Xavier Elon · 9:28 · 1K views
Leetcode 1315: Sum of Nodes with Even-Valued GrandparentAlgorithms Casts · 10:24 · 1K views
Leetcode Solution - 1315 Sum of Nodes with Even-Valued GrandparentJohn Leonardo · 4:33 · 575 views
Sum of Nodes with Even-Valued Grandparent | Tree | DFS | Leetcode | Algorithm UnlockAlgorithm Unlock · 17:18 · 381 views
Leetcode 1315. Sum of Nodes with Even-Valued GrandparentSatyam Bhardwaj · 6:53 · 341 views
Leetcode Problem - 1315 | Sum of Nodes with Even-Valued Grandparent | C++ | Top Interview Questionsvikas malinda · 4:15 · 204 views
LeetCode 1315 Sum of Nodes with Even Valued Grandparent - Recursion and List SolutionAlgorithmicIQ · 4:36 · 203 views
sum of nodes with even-valued grandparent - leetcode solutionCode feed · 7:20 · 163 views
The problem
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Example 1:
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.
Example 2:
Input: root = [1] Output: 0
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 1 <= Node.val <= 100
Approach overview
Problem Overview: Given a binary tree, compute the sum of all nodes whose grandparent node has an even value. For every node, you need to know the value of its parent and grandparent while traversing the tree.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
The cleanest solution uses Depth-First Search. While traversing the tree, carry two extra pieces of information: the parent value and the grandparent value. At each node, check whether the grandparent exists and whether its value is even. If it is, add the current node's value to the running sum. Then recurse into the left and right children while shifting the ancestry: the current node becomes the parent, and the parent becomes the grandparent.
This approach works because every node is visited exactly once, and the required condition can be evaluated immediately during traversal. The recursion stack depth equals the tree height h, so the space complexity is O(h). In a balanced tree this is O(log n), while in the worst case (skewed tree) it becomes O(n). The method is concise and maps naturally to recursive tree traversal.
Approach 2: Iterative Level Order Traversal (BFS) (Time: O(n), Space: O(n))
An iterative solution uses Breadth-First Search with a queue. Each queue entry stores three values: the current node, its parent value, and its grandparent value. When dequeuing a node, check whether the grandparent value is even; if so, add the node's value to the total. Then enqueue the left and right children with updated ancestry information.
This level-order traversal avoids recursion and processes nodes layer by layer. Because the queue can hold an entire tree level at once, the space complexity is O(n) in the worst case. The advantage is explicit control over traversal and no reliance on the call stack, which some engineers prefer for very deep trees.
Recommended for interviews: The recursive DFS approach is usually the expected answer. Passing the parent and grandparent values through recursion shows a strong understanding of tree traversal and avoids unnecessary data structures. BFS is equally correct but slightly more verbose due to queue bookkeeping.
Approach 1: Recursive Depth-First Search (DFS)
This approach uses a depth-first search traversal to keep track of the current node's parent and grandparent values. If the grandparent's value is even, the node's value is added to the sum.
We initiate the DFS with the root, setting initial parent and grandparent values as null or zero.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumEvenGrandparent(root: TreeNode) -> int:
def dfs(node, parent, grandparent):
if not node:
return 0
total = 0
if grandparent and grandparent.val % 2 == 0:
total += node.val
total += dfs(node.left, node, parent)
total += dfs(node.right, node, parent)
return total
return dfs(root, None, None)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int sumEvenGrandparent(TreeNode root) {
return dfs(root, null, null);
}
private int dfs(TreeNode node, TreeNode parent, TreeNode grandparent) {
if (node == null) return 0;
int sum = 0;
if (grandparent != null && grandparent.val % 2 == 0) {
sum += node.val;
}
sum += dfs(node.left, node, parent);
sum += dfs(node.right, node, parent);
return sum;
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
return dfs(root, nullptr, nullptr);
}
private:
int dfs(TreeNode* node, TreeNode* parent, TreeNode* grandparent) {
if (!node) return 0;
int sum = 0;
if (grandparent && grandparent->val % 2 == 0) {
sum += node->val;
}
sum += dfs(node->left, node, parent);
sum += dfs(node->right, node, parent);
return sum;
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var sumEvenGrandparent = function(root) {
function dfs(node, parent, grandparent) {
if (!node) return 0;
let total = 0;
if (grandparent && grandparent.val % 2 === 0) {
total += node.val;
}
total += dfs(node.left, node, parent);
total += dfs(node.right, node, parent);
return total;
}
return dfs(root, null, null);
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int dfs(struct TreeNode* node, struct TreeNode* parent, struct TreeNode* grandparent) {
if (!node) return 0;
int sum = 0;
if (grandparent && grandparent->val % 2 == 0) {
sum += node->val;
}
sum += dfs(node->left, node, parent);
sum += dfs(node->right, node, parent);
return sum;
}
int sumEvenGrandparent(struct TreeNode* root) {
return dfs(root, NULL, NULL);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int SumEvenGrandparent(TreeNode root) {
return DFS(root, null, null);
}
private int DFS(TreeNode node, TreeNode parent, TreeNode grandparent) {
if (node == null) return 0;
int sum = 0;
if (grandparent != null && grandparent.val % 2 == 0) {
sum += node.val;
}
sum += DFS(node.left, node, parent);
sum += DFS(node.right, node, parent);
return sum;
}
}In this code, we define a helper method dfs that takes the current node, its parent, and the grandparent node as arguments. We traverse the tree recursively, checking if the grandparent node exists and has an even value. If so, we add the current node's value to the total sum. The function returns the computed sum for all nodes valid under the given condition.
Time Complexity: O(n) where n is the number of nodes. Each node is visited once.
Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
Approach 2: Iterative Approach with Level Order Traversal
Utilizing an iterative method with breadth-first traversal (via a queue) enables level-wise examination of tree nodes. This format offers insight into parent-grandchild relations by leveraging node attributes over iteration.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumEvenGrandparent(root: TreeNode) -> int:
queue = deque([(root, None, None)])
total = 0
while queue:
node, parent, grandparent = queue.popleft()
if not node:
continue
if grandparent and grandparent.val % 2 == 0:
total += node.val
queue.append((node.left, node, parent))
queue.append((node.right, node, parent))
return totalimport java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int sumEvenGrandparent(TreeNode root) {
Queue<TreeNode[]> queue = new LinkedList<>();
queue.add(new TreeNode[]{root, null, null});
int sum = 0;
while (!queue.isEmpty()) {
TreeNode[] current = queue.poll();
TreeNode node = current[0], parent = current[1], grandparent = current[2];
if (node == null) continue;
if (grandparent != null && grandparent.val % 2 == 0) {
sum += node.val;
}
queue.add(new TreeNode[]{node.left, node, parent});
queue.add(new TreeNode[]{node.right, node, parent});
}
return sum;
}
}#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumEvenGrandparent(TreeNode* root) {
queue<pair<TreeNode*, pair<TreeNode*, TreeNode*>>> q;
q.push({root, {nullptr, nullptr}});
int sum = 0;
while (!q.empty()) {
auto [node, parentGrandparent] = q.front();
q.pop();
TreeNode* parent = parentGrandparent.first;
TreeNode* grandparent = parentGrandparent.second;
if (!node) continue;
if (grandparent && grandparent->val % 2 == 0) {
sum += node->val;
}
q.push({node->left, {node, parent}});
q.push({node->right, {node, parent}});
}
return sum;
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var sumEvenGrandparent = function(root) {
let queue = [{ node: root, parent: null, grandparent: null }];
let total = 0;
while (queue.length > 0) {
let { node, parent, grandparent } = queue.shift();
if (!node) continue;
if (grandparent && grandparent.val % 2 === 0) {
total += node.val;
}
queue.push({ node: node.left, parent: node, grandparent: parent });
queue.push({ node: node.right, parent: node, grandparent: parent });
}
return total;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
#define MAX_QUEUE_SIZE 10000
typedef struct {
struct TreeNode* node;
struct TreeNode* parent;
struct TreeNode* grandparent;
} QueueNode;
int sumEvenGrandparent(struct TreeNode* root) {
QueueNode queue[MAX_QUEUE_SIZE];
int front = 0, rear = 0;
queue[rear++] = (QueueNode){root, NULL, NULL};
int sum = 0;
while (front < rear) {
QueueNode current = queue[front++];
struct TreeNode* node = current.node;
struct TreeNode* parent = current.parent;
struct TreeNode* grandparent = current.grandparent;
if (!node) continue;
if (grandparent && grandparent->val % 2 == 0) {
sum += node->val;
}
if (rear < MAX_QUEUE_SIZE) { // Ensure capacity
queue[rear++] = (QueueNode){node->left, node, parent};
}
if (rear < MAX_QUEUE_SIZE) {
queue[rear++] = (QueueNode){node->right, node, parent};
}
}
return sum;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int SumEvenGrandparent(TreeNode root) {
Queue<(TreeNode, TreeNode, TreeNode)> queue = new Queue<(TreeNode, TreeNode, TreeNode)>();
queue.Enqueue((root, null, null));
int sum = 0;
while (queue.Count > 0) {
var (node, parent, grandparent) = queue.Dequeue();
if (node == null) continue;
if (grandparent != null && grandparent.val % 2 == 0) {
sum += node.val;
}
queue.Enqueue((node.left, node, parent));
queue.Enqueue((node.right, node, parent));
}
return sum;
}
}This Python implementation leverages a queue to perform level-order traversal. Pairs of node, parent, grandparent are used to track lineage and compute the sum for nodes with even-valued grandparents.
Time Complexity: O(n), where n is the count of nodes due to single node examination.
Space Complexity: O(w), w being the maximum width of the tree, accounting for queue storage.
Approach 3: DFS
We design a function dfs(root, x), which represents the sum of the values of the nodes that meet the conditions in the subtree with root as the root node and x as the value of the parent node of root. The answer is dfs(root, 1).
The execution process of the function dfs(root, x) is as follows:
- If
rootis null, return0. - Otherwise, we recursively calculate the answers of the left and right subtrees of
root, that is,dfs(root.left, root.val)anddfs(root.right, root.val), and add them to the answer. Ifxis even, we check whether the left and right children ofrootexist. If they exist, we add their values to the answer. - Finally, return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sumEvenGrandparent(root: TreeNode | null): number {
const dfs = (root: TreeNode | null, x: number): number => {
if (!root) {
return 0;
}
const { val, left, right } = root;
let ans = dfs(left, val) + dfs(right, val);
if (x % 2 === 0) {
ans += left?.val ?? 0;
ans += right?.val ?? 0;
}
return ans;
};
return dfs(root, 1);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumEvenGrandparent(root *TreeNode) int {
var dfs func(*TreeNode, int) int
dfs = func(root *TreeNode, x int) int {
if root == nil {
return 0
}
ans := dfs(root.Left, root.Val) + dfs(root.Right, root.Val)
if x%2 == 0 {
if root.Left != nil {
ans += root.Left.Val
}
if root.Right != nil {
ans += root.Right.Val
}
}
return ans
}
return dfs(root, 1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n) where n is the number of nodes. Each node is visited once. |
| Iterative Approach with Level Order Traversal | Time Complexity: O(n), where n is the count of nodes due to single node examination. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best general solution. Clean recursion with parent and grandparent tracking. |
| Iterative Level Order Traversal (BFS) | O(n) | O(n) | Useful when avoiding recursion or when processing nodes level by level. |
Frequently asked questions
Is Sum of Nodes with Even-Valued Grandparent easy or hard?
The problem is classified as Medium on LeetCode but has a high acceptance rate around 85%. The main challenge is recognizing that you must track ancestor values during traversal. Once that idea is clear, the implementation is straightforward using DFS or BFS.
Sum of Nodes with Even-Valued Grandparent Python/Java solution
Both Python and Java implementations typically use DFS recursion. The function receives the current node, parent value, and grandparent value. If the grandparent is even, the node value is added to the sum, then the function recursively processes the left and right children.
How to solve Sum of Nodes with Even-Valued Grandparent in O(n)?
Traverse the binary tree once while tracking the parent and grandparent values. For each node, check whether the grandparent exists and whether its value is divisible by 2. If it is even, add the current node value to the total sum. Both DFS recursion and BFS with a queue achieve O(n) time.
What is the best approach for Sum of Nodes with Even-Valued Grandparent?
Recursive Depth-First Search (DFS) is the most common approach. During traversal you pass the parent and grandparent values to each recursive call. If the grandparent value is even, add the current node value to the sum. This solution runs in O(n) time and uses O(h) recursion stack space.
Is Sum of Nodes with Even-Valued Grandparent asked at Google/Amazon/Meta?
Tree traversal problems with ancestor tracking frequently appear in interviews at companies like Amazon, Google, and Meta. Variations include checking parent conditions, grandparent conditions, or accumulating values based on ancestor properties. The core skill tested is binary tree traversal with additional state.
What data structure is used in Sum of Nodes with Even-Valued Grandparent?
The primary data structure is a binary tree. Solutions rely on traversal techniques such as Depth-First Search (DFS) using recursion or Breadth-First Search (BFS) using a queue. Additional variables track parent and grandparent values during traversal.
What is the time complexity of Sum of Nodes with Even-Valued Grandparent?
The time complexity is O(n) because every node in the binary tree is visited exactly once. Each visit performs a constant-time check to determine whether the grandparent value is even. Space complexity is O(h) for recursive DFS or O(n) for BFS depending on the traversal method.