Sum of Nodes with Even-Valued Grandparent

Sum of Nodes with Even-Valued Grandparent

What is this problem about?

In this tree-based challenge, you are given a binary tree. Your goal is to find the sum of all nodes that have an "even-valued grandparent." A node's grandparent is the parent of its parent. If a node has a grandparent and that grandparent's value is an even number, the node's value should be added to the total sum.

Why is this asked in interviews?

Companies like Microsoft, Meta, and Salesforce ask this problem to test a candidate's ability to traverse a tree while maintaining context from ancestor nodes. It's a classic example of how to pass information down a recursive call stack. It evaluates whether you can handle the "lookback" logic without actually storing a full path for every node, which would be memory-inefficient.

Algorithmic pattern used

The primary pattern is Depth-First Search (DFS) with state propagation. As you traverse the tree, each recursive call passes two additional pieces of information: the value of the current node's parent and the value of the current node's grandparent.

• When visiting node u, if grandparent_val is even, add u.val to the sum.
• When moving to children of u, the current u.val becomes the "parent" for the children, and the current "parent" becomes the "grandparent."

Example explanation

Consider the following tree fragment: 6 (Grandparent) / 7 (Parent) /
2 7 (Nodes to check)

1. At node 6: No parent/grandparent.
2. At node 7: Parent is 6, no grandparent.
3. At node 2: Parent is 7, grandparent is 6. Since 6 is even, add 2 to sum.
4. At node 7 (leaf): Parent is 7, grandparent is 6. Since 6 is even, add 7 to sum. Total Sum = 9.

Common mistakes candidates make

1. Trying to "look up": Attempting to find a node's grandparent by going up the tree. In a standard binary tree, nodes only have pointers to children, not parents.
2. Manually checking grandchildren: At an even node, checking node.left.left, node.left.right, etc. This leads to many null-pointer checks and messy code. Passing state down is much cleaner.
3. Missing root cases: Forgetting that nodes at depth 0 and 1 cannot have grandparents.

Interview preparation tip

Practice passing "state" through recursion. Many tree and graph problems require knowing something about the path taken to reach the current node. This technique avoids the need for complex "parent" pointers or global arrays.