Sum of Nodes with Even-Valued Grandparent

medium binary tree dfs recursion

Problem

Given the root of a binary tree, return the sum of the values of every node whose grandparent (its parent's parent) has an even value. If there is no such node, return 0.

Inputroot = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]

Output18

Grandparent 6 contributes its grandchildren 2, 7, 1, 3; grandparent 8 contributes 5. Sum = 2+7+1+3+5 = 18.

tree (level-order, use null for gaps)

def sumEvenGrandparent(root):
    def dfs(node, parent, grand):
        if not node:
            return 0
        total = 0
        if grand is not None and grand % 2 == 0:
            total += node.val
        total += dfs(node.left, node.val, parent)
        total += dfs(node.right, node.val, parent)
        return total
    return dfs(root, None, None)

function sumEvenGrandparent(root) {
  function dfs(node, parent, grand) {
    if (!node) return 0;
    let total = 0;
    if (grand !== null && grand % 2 === 0) {
      total += node.val;
    }
    total += dfs(node.left, node.val, parent);
    total += dfs(node.right, node.val, parent);
    return total;
  }
  return dfs(root, null, null);
}

int sumEvenGrandparent(TreeNode root) {
    return dfs(root, -1, -1);
}

int dfs(TreeNode node, int parent, int grand) {
    if (node == null) return 0;
    int total = 0;
    if (grand != -1 && grand % 2 == 0) {
        total += node.val;
    }
    total += dfs(node.left, node.val, parent);
    total += dfs(node.right, node.val, parent);
    return total;
}

int dfs(TreeNode* node, int parent, int grand) {
    if (!node) return 0;
    int total = 0;
    if (grand != -1 && grand % 2 == 0) {
        total += node->val;
    }
    total += dfs(node->left, node->val, parent);
    total += dfs(node->right, node->val, parent);
    return total;
}

int sumEvenGrandparent(TreeNode* root) {
    return dfs(root, -1, -1);
}

Explanation

A node is counted only when we know the value of its grandparent. The neat trick is that, while doing one ordinary depth-first traversal, each call can carry down the two ancestor values it needs.

The helper dfs(node, parent, grand) receives the current node together with the value of its parent and its grandparent. When we recurse into a child, the child's parent becomes the current node's value and the child's grandparent becomes the current node's parent value — so the window of ancestors simply slides down one level.

At each non-null node we check a single condition: if grand exists and grand % 2 == 0, the node qualifies and we add node.val to the running total. Then we add the results of recursing left and right.

The root and its direct children have no grandparent, so they never qualify on their own — only nodes at depth 2 or deeper can be added. In the languages without a null sentinel for ints (Java, C++) we pass -1 to mean “no ancestor yet,” which is safe because tree values are non-negative.

Every node is visited exactly once, so the work is linear in the number of nodes, and the only extra space is the recursion stack proportional to the tree's height.

Time: O(n) Space: O(h)