Sum of Nodes with Even-Valued Grandparent
MedPrompt
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
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
rootisnull, 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
nodein the map's key set (which represents all nodes except the root). - Get its
parentfrom the map. - Get the
grandparent(parent of the parent) from the map. - If a
grandparentexists and its value is even, add the currentnode.valtosum. - 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.
/** * 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 { public int sumEvenGrandparent(TreeNode root) { if (root == null) { return 0; } Map<TreeNode, TreeNode> parentMap = new HashMap<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); parentMap.put(root, null); // Root has no parent while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node.left != null) { parentMap.put(node.left, node); queue.offer(node.left); } if (node.right != null) { parentMap.put(node.right, node); queue.offer(node.right); } } int sum = 0; for (TreeNode node : parentMap.keySet()) { TreeNode parent = parentMap.get(node); if (parent != null) { TreeNode grandparent = parentMap.get(parent); if (grandparent != null && grandparent.val % 2 == 0) { sum += node.val; } } } return sum; }}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.
This approach traverses the tree only once using Depth-First Search (DFS). It uses a recursive helper function that keeps track of the current node's parent and grandparent. By passing this information down during the recursion, each node can check its grandparent's value directly.
Algorithm
- Initialize a member variable
sum = 0. - Define a recursive function
dfs(node, parent, grandparent). - Start the process by calling
dfs(root, null, null). - Inside
dfs:- If
nodeisnull, return. - If
grandparentis notnullandgrandparent.valis even, addnode.valtosum. - Make a recursive call for the left child:
dfs(node.left, node, parent). - Make a recursive call for the right child:
dfs(node.right, node, parent).
- If
- After the initial call completes, return
sum.
Walkthrough
We can solve the problem in a single pass by carrying the necessary context down the tree. A recursive DFS function is a natural fit for this. We define a helper function, dfs(current, parent, grandparent).
The main function starts the process by calling dfs(root, null, null), as the root has no parent or grandparent.
Inside the dfs function:
- We handle the base case: if
currentisnull, we stop that path of recursion. - We check if a
grandparentwas passed (i.e., is notnull) and if its value is even. If so, thecurrentnode is a grandchild of an even-valued grandparent, and we add its value to a running total. - We then proceed to the next level of the tree by making recursive calls for the children. For the call on
current.left, thecurrentnode becomes the newparent, and the oldparentbecomes the newgrandparent. The same logic applies to the call oncurrent.right.
This ensures every node is visited once, and the check is performed efficiently using the information passed down the recursion stack.
/** * 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 { int sum = 0; public int sumEvenGrandparent(TreeNode root) { dfs(root, null, null); return sum; } private void dfs(TreeNode current, TreeNode parent, TreeNode grandparent) { if (current == null) { return; } if (grandparent != null && grandparent.val % 2 == 0) { sum += current.val; } // The current node becomes the parent, and the parent becomes the grandparent for the next level. dfs(current.left, current, parent); dfs(current.right, current, parent); }}Complexity
Time
O(N), as each node in the tree is visited exactly once.
Space
O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
Trade-offs
Pros
Efficient in time, as it traverses the tree only once.
More space-efficient than the two-pass approach, especially for balanced trees.
Cons
The recursion can lead to a
StackOverflowErrorfor very deep, skewed trees.The state (parent, grandparent) needs to be passed through function arguments, making the function signature more complex.
This is the most efficient approach, performing the calculation in a single pass without explicitly passing parent/grandparent pointers. During the traversal (either DFS or BFS), whenever we encounter a node with an even value, we treat it as a potential grandparent. We then look ahead to its grandchildren and, if they exist, add their values to the total sum.
Algorithm
- This can be implemented with either DFS or BFS.
- DFS (Recursive) Algorithm:
- Base Case: If the current
nodeisnull, return 0. - Initialize a local
sum = 0. - If
node.valis even:- Check for the four possible grandchildren. If a grandchild exists, add its value to
sum.
- Check for the four possible grandchildren. If a grandchild exists, add its value to
- Recursively call the function for the left child and add the result to
sum. - Recursively call the function for the right child and add the result to
sum. - Return the total
sum.
- Base Case: If the current
- BFS (Iterative) Algorithm:
- Initialize
sum = 0and aQueuewith theroot. - While the queue is not empty:
- Dequeue a
node. - If
node.valis even, check for its grandchildren and add their values tosum. - Enqueue the node's non-null children.
- Dequeue a
- Initialize
Walkthrough
This optimal solution traverses the tree once and calculates the sum directly. Instead of a grandchild looking up at its grandparent, we make the grandparent look down at its grandchildren. This simplifies the logic and the state we need to maintain.
We can use any standard traversal, like DFS or BFS. Let's consider a recursive DFS implementation. We define a traversal function that takes a node as input.
Inside the function:
- Handle the base case: if the node is
null, return. - Check if the current
node's value is even. If it is, this node is an even-valued grandparent. We then check for the existence of its grandchildren and add their values to our sum.- Check
node.left.leftandnode.left.right. - Check
node.right.leftandnode.right.right.
- Check
- Crucially, regardless of the current node's value, we must continue the traversal to its children (
node.leftandnode.right) because there might be other even-valued grandparents deeper in the tree.
This method is efficient because each node is visited once, and for each node, we only perform a few constant-time checks on its immediate children and grandchildren.
/** * 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 { public int sumEvenGrandparent(TreeNode root) { if (root == null) return 0; int sum = 0; // Check if the current node is an even-valued grandparent if (root.val % 2 == 0) { if (root.left != null) { if (root.left.left != null) sum += root.left.left.val; if (root.left.right != null) sum += root.left.right.val; } if (root.right != null) { if (root.right.left != null) sum += root.right.left.val; if (root.right.right != null) sum += root.right.right.val; } } // Recursively call for children and add their results sum += sumEvenGrandparent(root.left); sum += sumEvenGrandparent(root.right); return sum; }}Complexity
Time
O(N), as each node is visited exactly once.
Space
O(H) for recursive DFS (due to the call stack) or O(W) for iterative BFS (due to the queue), where H is the tree height and W is its maximum width. In the worst case, this is O(N).
Trade-offs
Pros
Most efficient approach with a single pass over the tree.
Simple recursive function signature (
(TreeNode node)), which is clean and avoids passing extra state.Can be easily implemented both recursively (DFS) and iteratively (BFS).
Cons
The logic inside the traversal function involves several nested
ifchecks for grandchildren, which can appear slightly verbose.
Solutions
Solution
/** * 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 ); } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int res ; int sumEvenGrandparent ( TreeNode * root ) { res = 0 ; dfs ( root , root -> left ); dfs ( root , root -> right ); return res ; } void dfs ( TreeNode * g , TreeNode * p ) { if ( ! p ) return ; if ( g -> val % 2 == 0 ) { if ( p -> left ) res += p -> left -> val ; if ( p -> right ) res += p -> right -> val ; } dfs ( p , p -> left ); dfs ( p , p -> right ); } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def sumEvenGrandparent ( self , root : TreeNode ) -> int : self . res = 0 def dfs ( g , p ): if p is None : return if g . val % 2 == 0 : if p . left : self . res += p . left . val if p . right : self . res += p . right . val dfs ( p , p . left ) dfs ( p , p . right ) dfs ( root , root . left ) dfs ( root , root . right ) return self . resVideo 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.