Problem

Given the root of a binary tree, return the sum of values of nodes with aneven-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.

Examples

Example 1

flowchart TD
    %% styles
    classDef gp fill:#cfe9ff,stroke:#2b6fb3,stroke-width:1px;
    classDef counted fill:#ffd2d2,stroke:#b33b3b,stroke-width:1px;
    classDef normal fill:#fff,stroke:#333,stroke-width:1px;
    classDef hidden display:none;

    A("6"):::gp
    A --- B("7"):::normal & C("8"):::gp

    B --- D("2"):::counted & E("7"):::counted

    C --- F("1"):::counted & G("3"):::counted

    D --- H("9"):::normal
    D ~~~ N1:::hidden

    E --- I("1"):::normal & J("4"):::normal

    G ~~~ N2:::hidden
    G --- K("5"):::counted
  
1
2
3

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

flowchart TD
    classDef normal fill:#fff,stroke:#333,stroke-width:1px;
    A(1):::normal
  
1
2

Input: root = [1]
Output: 0

Constraints

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

Solution

Method 1 - DFS (Pass Parent & Grandparent)

Approach

We use DFS or BFS to traverse the tree, passing down the parent and grandparent values. If the grandparent is even, add the current node’s value to the running result res.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(h) where h is the height of the tree

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) {
        if (!root) return 0;
        int res = (gp % 2 == 0) ? root->val : 0;
        res += sumEvenGrandparent(root->left, root->val, p);
        res += sumEvenGrandparent(root->right, root->val, p);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return dfs(root, 1, 1);
    }
    private int dfs(TreeNode node, int parent, int grandparent) {
        if (node == null) return 0;
        int res = (grandparent % 2 == 0) ? node.val : 0;
        res += dfs(node.left, node.val, parent);
        res += dfs(node.right, node.val, parent);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
class Solution {
    fun sumEvenGrandparent(root: TreeNode?): Int {
        fun dfs(node: TreeNode?, parent: Int, grandparent: Int): Int {
            if (node == null) return 0
            var res = if (grandparent % 2 == 0) node.`val` else 0
            res += dfs(node.left, node.`val`, parent)
            res += dfs(node.right, node.`val`, parent)
            return res
        }
        return dfs(root, 1, 1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(node, parent, grandparent):
            if not node:
                return 0
            res = node.val if grandparent % 2 == 0 else 0
            res += dfs(node.left, node.val, parent)
            res += dfs(node.right, node.val, parent)
            return res
        return dfs(root, 1, 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Definition for a binary tree node.
// struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sum_even_grandparent(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, parent: i32, grandparent: i32) -> i32 {
            if let Some(n) = node {
                let n = n.borrow();
                let mut res = if grandparent % 2 == 0 { n.val } else { 0 };
                res += dfs(n.left.clone(), n.val, parent);
                res += dfs(n.right.clone(), n.val, parent);
                res
            } else { 0 }
        }
        dfs(root, 1, 1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}
function sumEvenGrandparent(root: TreeNode | null): number {
    function dfs(node: TreeNode | null, parent: number, grandparent: number): number {
        if (!node) return 0
        let res = grandparent % 2 === 0 ? node.val : 0
        res += dfs(node.left, node.val, parent)
        res += dfs(node.right, node.val, parent)
        return res
    }
    return dfs(root, 1, 1)
}