Depth First Search Algorithm to Compute the Sum of Nodes with Even Grandparent Values

Given a binary tree root, return the sum of all node values whose grandparents have an even value.

Constraints
0 ≤ n ≤ 100,000 where n is the number of nodes in root
Example 1
Input
Visualize

root =

      8
     / \
    4   3
   / \
  6   7
       \
        2

Output
15
Explanation
Nodes 6, 7, and 2 have an even value grandparent.

Depth First Search Algorithm to Sum the Nodes of Even GrandParents

We can perform a Depth First Search Algorithm on the Binary Tree and pass down the GrantParent node. The current node will become parent, and parent node will become grandparent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int sumNodesOfEvenGrandParents(Tree* root) {
    int ans = 0;
    function<void(Tree*, Tree*, Tree*)> dfs = [&](Tree* root, Tree* parent, Tree* grandparent) {
        if (!root) return;
        if (grandparent!= NULL && ((grandparent->val & 1) == 0)) {
            ans += root->val;
        }
        dfs(root->left, root, parent);
        dfs(root->right, root, parent);
    };
    dfs(root, NULL, NULL);
    return ans;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int sumNodesOfEvenGrandParents(Tree* root) {
    int ans = 0;
    function<void(Tree*, Tree*, Tree*)> dfs = [&](Tree* root, Tree* parent, Tree* grandparent) {
        if (!root) return;
        if (grandparent!= NULL && ((grandparent->val & 1) == 0)) {
            ans += root->val;
        }
        dfs(root->left, root, parent);
        dfs(root->right, root, parent);
    };
    dfs(root, NULL, NULL);
    return ans;
}

The time complexity is O(N) where N is the number of the nodes in the binary tree (we need to visit each node exactly once) and the space complexity is O(N) because we are using stack implicitly due to Recursion.

–EOF (The Ultimate Computing & Technology Blog)