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:
[1, 104].1 <= Node.val <= 100Problem 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.
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.
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.
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.
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.
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:
root is null, return 0.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.The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
1315. Sum of Nodes with Even-Valued Grandparent | BINARY TREE | LEETCODE MEDIUM | CODE EXPLAINER • code Explainer • 3,338 views views
Watch 9 more video solutions →Practice Sum of Nodes with Even-Valued Grandparent with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor