Sum of Nodes with Even-Valued Grandparent

Med

#1224Time: O(N), where N is the number of nodes. The first pass to build the map takes O(N), and the second pass to iterate and sum takes O(N).Space: O(N). The `parentMap` stores N-1 entries. The queue for BFS can also hold up to O(N) nodes in the worst case (for a complete binary tree).

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This method uses two passes over the tree. The first pass builds a map to link each node to its parent. The second pass then uses this map to find the grandparent for each node and sums up the values of nodes with an even-valued grandparent.

Algorithm

If the root is null, return 0.
Create a Map<TreeNode, TreeNode> to store parent pointers.
Use a queue for BFS to traverse the tree, starting with the root.
In the BFS loop, for each node, populate the parent map for its children.
Initialize sum = 0.
Iterate through each node in the map's key set (which represents all nodes except the root).
Get its parent from the map.
Get the grandparent (parent of the parent) from the map.
If a grandparent exists and its value is even, add the current node.val to sum.
Return sum.

Walkthrough

This approach first builds a complete map of parent pointers for every node in the tree. This is done by traversing the tree once, for instance, using Breadth-First Search (BFS), and storing (child, parent) pairs in a HashMap.

After the map is built, we iterate through all nodes that have a parent. For each node, we look up its parent in the map. If a parent exists, we look up the parent's parent (the grandparent). If the grandparent also exists and its value is even, we add the current node's value to our total sum.

While this approach correctly solves the problem, it is suboptimal due to its space and time overhead. It requires O(N) extra space for the map and it traverses all nodes twice.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int sumEvenGrandparent(TreeNode root) {18        if (root == null) {19            return 0;20        }21 22        Map<TreeNode, TreeNode> parentMap = new HashMap<>();23        Queue<TreeNode> queue = new LinkedList<>();24        queue.offer(root);25        parentMap.put(root, null); // Root has no parent26 27        while (!queue.isEmpty()) {28            TreeNode node = queue.poll();29            if (node.left != null) {30                parentMap.put(node.left, node);31                queue.offer(node.left);32            }33            if (node.right != null) {34                parentMap.put(node.right, node);35                queue.offer(node.right);36            }37        }38        39        int sum = 0;40        for (TreeNode node : parentMap.keySet()) {41            TreeNode parent = parentMap.get(node);42            if (parent != null) {43                TreeNode grandparent = parentMap.get(parent);44                if (grandparent != null && grandparent.val % 2 == 0) {45                    sum += node.val;46                }47            }48        }49        50        return sum;51    }52}

Complexity

Time

O(N), where N is the number of nodes. The first pass to build the map takes O(N), and the second pass to iterate and sum takes O(N).

Space

O(N). The `parentMap` stores N-1 entries. The queue for BFS can also hold up to O(N) nodes in the worst case (for a complete binary tree).

Trade-offs

Pros

The logic is separated into two distinct and easy-to-understand steps: building parent relationships and then calculating the sum.

Cons

Inefficient due to requiring two full passes over the tree's nodes.
Requires O(N) extra space for the parent map, which is generally worse than single-pass solutions that use O(H) space.

Solutions

Solution

1/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { private int res ; public int sumEvenGrandparent ( TreeNode root ) { res = 0 ; dfs ( root , root . left ); dfs ( root , root . right ); return res ; } private void dfs ( TreeNode g , TreeNode p ) { if ( p == null ) { return ; } if ( g . val % 2 == 0 ) { if ( p . left != null ) { res += p . left . val ; } if ( p . right != null ) { res += p . right . val ; } } dfs ( p , p . left ); dfs ( p , p . right ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem