LietCode
Sum of Nodes with Even-Valued Grandparent (Medium)

Sum of Nodes with Even-Valued Grandparent (Medium)

Abhi's photo
Abhi
·

3 min read

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: 18
Explanation: 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

1) Explain the problem

We need to find the sum of the values of all nodes in a binary tree that have an even-valued grandparent. If no such nodes exist, return 0. A grandparent is defined as the parent of a node's parent.

2) Short easy to remember solution/approach

Use a depth-first search (DFS) to traverse the tree. For each node, check if its grandparent (if it exists) has an even value. If yes, add the node's value to the sum.

3) Solution in Javascript with code commenting

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function sumEvenGrandparent(root) {
    function dfs(node, parent, grandparent) {
        if (!node) return 0;

        // Initialize the sum
        let sum = 0;

        // Check if the grandparent exists and has an even value
        if (grandparent && grandparent.val % 2 === 0) {
            sum += node.val;
        }

        // Recur for left and right children with updated parent and grandparent
        sum += dfs(node.left, node, parent);
        sum += dfs(node.right, node, parent);

        return sum;
    }

    // Start DFS with null parent and grandparent
    return dfs(root, null, null);
}

// Example usage:
let root = new TreeNode(6);
root.left = new TreeNode(7);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(1);
root.right.right = new TreeNode(3);
root.left.left.left = new TreeNode(9);
root.left.right.left = new TreeNode(1);
root.left.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(5);

console.log(sumEvenGrandparent(root)); // Output: 18

4) Explanation of the solution in an easy-to-understand way. Explain it like a 10yo.

Imagine you have a big family tree, and you want to find out how much candy your cousins with even-numbered grandparents have. You start from the top of the tree and go down each branch, checking if the grandparent's number is even. If it is, you count the candy that cousin has. You keep going until you've checked everyone.

5) Code explanation in pointers

  • Define a TreeNode class to represent each node in the tree.

  • Create a sumEvenGrandparent function that:

    • Defines a helper function dfs to:

      • Return 0 if the node is null (base case).

      • Initialize a sum variable to 0.

      • Check if the grandparent exists and has an even value. If yes, add the node's value to the sum.

      • Recursively calculate the sum for the left and right subtrees, updating the parent and grandparent.

      • Return the total sum.

    • Start the DFS traversal with the root node and null parent and grandparent.

  • Use the sumEvenGrandparent function to calculate the total sum of nodes with even-valued grandparents.

6) Complexities

  • Time Complexity: (O(n)) - Each node is visited once.

  • Space Complexity: (O(h)) - Where (h) is the height of the tree. This is due to the recursion stack.

TreeTrees