Problem Description

You are given the root of a binary tree. Your task is to find the sum of values of all nodes that have an even-valued grandparent.

A grandparent of a node is defined as the parent of its parent (if it exists). In other words, if a node has a parent, and that parent also has a parent, then that parent's parent is the node's grandparent.

The problem asks you to:

1. Traverse the binary tree
2. For each node, check if its grandparent exists and has an even value
3. If a node has an even-valued grandparent, include that node's value in the sum
4. Return the total sum of all such nodes

If there are no nodes with an even-valued grandparent in the tree, return 0.

For example, if a node with value 6 (which is even) has two children, and those children have their own children (the grandchildren of the node with value 6), then all those grandchildren should have their values included in the sum.

The solution uses a depth-first search (DFS) approach where it tracks the parent's value as it traverses the tree. When visiting a node, if the parent's parent (tracked from the previous recursive call) has an even value, the current node's children are the ones that should be added to the sum.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we have a root node and each node has at most two children (left and right).

DFS

• Since we're dealing with a tree structure, the flowchart directs us to use DFS (Depth-First Search).

Why DFS is appropriate for this problem:

• We need to traverse the entire tree to find all nodes with even-valued grandparents
• We need to track information about ancestors (specifically grandparents) as we traverse
• DFS naturally maintains the parent-child-grandchild relationship through its recursive call stack
• As we traverse down the tree, we can pass information about the parent and grandparent values to determine if current nodes should be included in the sum

Conclusion: The flowchart correctly suggests using DFS for this tree traversal problem. The DFS approach allows us to maintain the grandparent-parent-child relationship naturally through recursive calls, where we can pass the parent's value down to check if it's even when we reach the grandchildren nodes.

Intuition

The key insight is that when we're at a node, we can't directly check if its grandparent is even-valued because we typically only have access to the current node in a tree traversal. However, we can flip our perspective: instead of checking "does this node have an even-valued grandparent?", we can ask "if this node has an even value, which nodes should I add to the sum?"

When we're at a node with an even value, its grandchildren are the nodes that should be counted. But how do we access grandchildren? We can't directly jump two levels down. Instead, we can pass information down through the traversal.

The clever approach is to pass the parent's value as we traverse. Here's the reasoning:

• When we start at the root, we pass down the root's value to its children
• When we're at a child node, we receive its parent's value as a parameter
• If this parent value is even, then the current node's children are grandchildren of that even-valued node
• So we add the values of the current node's children to our sum

This way, we're essentially checking one generation ahead: "My parent has an even value, so my children are grandchildren of an even-valued node."

The initial call uses dfs(root, 1) with 1 as the parent value (which is odd) to ensure that the root's children aren't mistakenly counted, since the root itself has no grandparent.

This approach elegantly solves the problem in a single traversal by maintaining just enough context (the parent's value) to make the grandparent-grandchild relationship determination possible.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal with a clever parameter passing technique. Let's walk through the implementation step by step:

Function Design: We create a helper function dfs(root, x) where:

• root is the current node being processed
• x is the value of the parent node of root

Base Case: If root is None, we return 0 since there's nothing to process.

Recursive Traversal: For each node, we recursively calculate the sum for its left and right subtrees:

ans = dfs(root.left, root.val) + dfs(root.right, root.val)

Notice how we pass root.val as the second parameter - this means when we process the children, they'll know their parent's value.

Checking for Even Grandparent: The critical logic happens here:

if x % 2 == 0:
    if root.left:
        ans += root.left.val
    if root.right:
        ans += root.right.val

If x (the parent's value) is even, then the current node's children are grandchildren of that even-valued node. We add their values to our answer.

Initial Call: The solution starts with dfs(root, 1). We use 1 as the initial parent value because:

• 1 is odd, ensuring the root's children won't be mistakenly counted
• The root has no actual parent or grandparent

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, due to the recursive call stack

The elegance of this solution lies in how it tracks the grandparent relationship indirectly - by passing the parent value down and checking it when we're one level deeper, we effectively identify all nodes with even-valued grandparents.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary tree:

        6 (even)
       / \
      7   8
     / \   \
    2   4   5

We want to find the sum of all nodes with an even-valued grandparent.

Step 1: Start at root

• Call dfs(node_6, 1)
• Current node: 6, parent value: 1 (odd, dummy value)
• Since 1 is odd, we don't add node 6's children (7 and 8) to the sum
• Recursively process left child (7) and right child (8)

Step 2: Process node 7

• Call dfs(node_7, 6)
• Current node: 7, parent value: 6 (even!)
• Since 6 is even, we add node 7's children to the sum:
  • Left child: 2 (add to sum)
  • Right child: 4 (add to sum)
• Current sum = 2 + 4 = 6
• Recursively process children with parent value 7

Step 3: Process node 8

• Call dfs(node_8, 6)
• Current node: 8, parent value: 6 (even!)
• Since 6 is even, we add node 8's children to the sum:
  • Left child: None (skip)
  • Right child: 5 (add to sum)
• Current sum = 6 + 5 = 11
• Recursively process children with parent value 8

Step 4: Process leaf nodes (2, 4, 5)

• dfs(node_2, 7): parent 7 is odd, no children to add anyway
• dfs(node_4, 7): parent 7 is odd, no children to add anyway
• dfs(node_5, 8): parent 8 is even, but node 5 has no children

Final Result: 2 + 4 + 5 = 11

The nodes 2, 4, and 5 all have node 6 as their grandparent (which has an even value), so their values are included in the sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

• Checking if the node is null
• Checking if the parent value x is even using modulo operation
• Adding values of children nodes if they exist
• Making recursive calls to left and right children

Since we visit each of the n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the tree could be completely unbalanced (like a linked list), where all nodes are arranged in a single path. This would result in a recursion depth of n, requiring O(n) space on the call stack.

In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but since we consider worst-case complexity, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Tracking Grandparent Relationships

A common mistake is trying to track the grandparent node directly or passing both parent and grandparent values through the recursion. This leads to unnecessarily complex code:

Incorrect Approach:

def dfs(node, parent, grandparent):
    if not node:
        return 0
  
    total = dfs(node.left, node, parent) + dfs(node.right, node, parent)
  
    if grandparent and grandparent.val % 2 == 0:
        total += node.val
  
    return total

This approach requires passing node references and handling None cases, making the code more error-prone.

2. Wrong Level Checking

Another pitfall is checking at the wrong level of the tree. Some might incorrectly add the current node's value when its parent is even:

Incorrect Code:

if parent_val % 2 == 0:
    total_sum += node.val  # Wrong! This makes parent the grandparent

Correct Code:

if parent_val % 2 == 0:
    if node.left:
        total_sum += node.left.val  # Correct! Parent becomes grandparent to children
    if node.right:
        total_sum += node.right.val

3. Forgetting to Check Child Existence

A subtle but critical error is forgetting to check if children exist before accessing their values:

Incorrect Code:

if parent_val % 2 == 0:
    total_sum += node.left.val + node.right.val  # Will crash if either child is None

Correct Code:

if parent_val % 2 == 0:
    if node.left:
        total_sum += node.left.val
    if node.right:
        total_sum += node.right.val

4. Wrong Initial Parent Value

Using an even number (like 0 or 2) as the initial parent value would incorrectly count the root's children as having an even grandparent:

Incorrect:

return dfs(root, 0)  # Wrong! Will incorrectly add root's grandchildren

Correct:

return dfs(root, 1)  # Correct! Odd number prevents false counting

5. Alternative Solution Using Level Tracking

For those who find the parent-value passing confusing, here's an alternative approach that explicitly tracks the grandparent:

def sumEvenGrandparent(self, root: TreeNode) -> int:
    def dfs(node, parent_val, grandparent_val):
        if not node:
            return 0
      
        total = 0
      
        # Check if current node has an even grandparent
        if grandparent_val != -1 and grandparent_val % 2 == 0:
            total += node.val
      
        # Recurse with updated parent and grandparent values
        total += dfs(node.left, node.val, parent_val)
        total += dfs(node.right, node.val, parent_val)
      
        return total
  
    return dfs(root, -1, -1)  # Use -1 to indicate no parent/grandparent

While this approach is more explicit, it's also slightly less efficient due to passing an extra parameter.