Sponsored
Sponsored
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int dfs(struct TreeNode* node, struct TreeNode* parent, struct TreeNode* grandparent) {
11 if (!node) return 0;
12 int sum = 0;
13 if (grandparent && grandparent->val % 2 == 0) {
14 sum += node->val;
15 }
16 sum += dfs(node->left, node, parent);
17 sum += dfs(node->right, node, parent);
18 return sum;
19}
20
21int sumEvenGrandparent(struct TreeNode* root) {
22 return dfs(root, NULL, NULL);
23}This C code mirrors the logic laid out in other languages with a recursive function to sum nodes having even-value grandparents. The recursion passes the node, its parent, and grandparent, adding values under the mentioned condition.
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.
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.
1using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int SumEvenGrandparent(TreeNode root) {
Queue<(TreeNode, TreeNode, TreeNode)> queue = new Queue<(TreeNode, TreeNode, TreeNode)>();
queue.Enqueue((root, null, null));
int sum = 0;
while (queue.Count > 0) {
var (node, parent, grandparent) = queue.Dequeue();
if (node == null) continue;
if (grandparent != null && grandparent.val % 2 == 0) {
sum += node.val;
}
queue.Enqueue((node.left, node, parent));
queue.Enqueue((node.right, node, parent));
}
return sum;
}
}C# implements a traditional iterative approach via level-order traversal. Employing a queue, the pertinent nodes are examined level by level with accumulative operations on notes with even-valued grandparents.