Skip to main content
Talentd

Sum of Nodes with Even-Valued Grandparent - Solution & Explanation

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree18 min readAsked at: Amazon, Meta, Salesforce +1
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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 root is null, return 0.
  • Otherwise, we recursively calculate the answers of the left and right subtrees of root, that is, dfs(root.left, root.val) and dfs(root.right, root.val), and add them to the answer. If x is even, we check whether the left and right children of root exist. 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search (DFS)

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.

Iterative Approach with Level Order Traversal

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.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

1315. Sum of Nodes with Even-Valued Grandparent | BINARY TREE | LEETCODE MEDIUM | CODE EXPLAINER • code Explainer • 3,399 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sum of Nodes with Even-Valued Grandparent with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II