Skip to main content

Sum of Nodes with Even-Valued Grandparent

Problem statement​

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]Output: 18Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Example 2:

Input: root = [1]Output: 0

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 1 <= Node.val <= 100

My solution​

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumEvenGrandparent = function(root) {
    let sum = 0;
    let parentMap = new Map();
    
    function dfs(node, level) {
        if (!node) {
            return;
        }
        
        if (parentMap.get(level - 2)) {
            sum += node.val
        }
        
        if (node.val % 2 === 0) {
            parentMap.set(level, true)
        }
        
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
        
        if (parentMap.has(level)) {
            parentMap.set(level, false)
        }
    }
    
    dfs(root, 0)
    
    return sum
    
};