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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def sumEvenGrandparent(root: TreeNode) -> int:
8 def dfs(node, parent, grandparent):
9 if not node:
10 return 0
11 total = 0
12 if grandparent and grandparent.val % 2 == 0:
13 total += node.val
14 total += dfs(node.left, node, parent)
15 total += dfs(node.right, node, parent)
16 return total
17 return dfs(root, None, None)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.
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.
1
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.