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.

Description Hints 2 Solution Video 6:48

1315. Sum of Nodes with Even-Valued Grandparent

Medium85.6% acceptance4 companies

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, 10⁴].
1 <= Node.val <= 100

Asked at 4 companies

Josh Technology Salesforce Amazon Meta

Topics

Hints open one at a time

Hint 1

Traverse the tree keeping the parent and the grandparent.

Hint 2

If the grandparent of the current node is even-valued, add the value of this node to the answer.

6:48

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Input

[1]

Your code is saved on this device.Solution