Sum of Nodes with Even-Valued Grandparent - Video Solutions

Problem 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.