1315. Sum of Nodes with Even-Valued Grandparent

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem requires us to compute the sum of values of all nodes in a binary tree that have an even-valued grandparent. A grandparent of a node is defined as the parent of that node's parent, whenever such a relative exists. The binary tree is given by the root node, and we need to traverse the tree to find the nodes of interest and sum their values. If there are no nodes with an even-valued grandparent, the sum to be returned should be 0.

Flowchart Walkthrough

Let's use the provided algorithm flowchart to determine the appropriate search algorithm for LeetCode problem 1315, "Sum of Nodes with Even-Valued Grandparent." We'll walk through the decision-making process step by step, referencing the Flowchart.

Is it a graph?
- Yes: The problem involves a tree, which is a type of graph.
Is it a tree?
- Yes: The data structure mentioned in the problem is explicitly a binary tree.
Conclusion: The flowchart directs us from the "Is it a tree?" node to utilizing "DFS" (Depth-First Search) for navigating and processing this particular tree structure.

By following these prompts, we've concluded that Depth-First Search (DFS) is the correct approach for solving this problem, as the main structure involved is inherently a tree and the problem involves traversing it to perform computations based on certain conditions (i.e., even-valued grandparents). It should be effective in efficiently visiting each node to check and aggregate values as required by the problem's constraints.

Intuition

To solve this problem, the solution uses a Depth-First Search (DFS) traversal approach. This means we explore as far as possible down each branch before backtracking. This approach is suitable for binary trees because it allows us to maintain state information as we traverse each level of the tree, which is essential for identifying grandparents and their grandchildren.

The intuition behind using DFS in this problem is that we can keep track of the grandparent and parent of the current node as we traverse the tree. Whenever we identify a grandparent with an even value, we know that we have to check its grandchildren (the children of the current parent node) and add their values to our sum, if they exist.

The algorithm involves starting at the root of the tree, then recursively going through each branch, keeping track of the current node, its parent, and grandparent. We pass the current parent to be the grandparent in the next level of the recursive call, and the current node's children to be the parent in the next level. Whenever the current grandparent's value is even, we add the value of the current parent's children to the result.

This method requires a closure or an external variable to keep the sum while the recursion is taking place, as illustrated in the solution code with self.res, which is initialized to 0. As the recursion unfolds, self.res is updated whenever we are at nodes with an even-valued grandparent.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The provided Python solution implements a Depth-First Search (DFS) algorithm to traverse the binary tree and identify the nodes that contribute to the sum based on the even-valued grandparent condition. Here's a step-by-step breakdown of how the code works, aligning with common practices in DFS algorithms:

Initialization: A variable self.res is defined at the class level to keep track of the cumulative sum of all nodes meeting the criteria (nodes with even-valued grandparents).
DFS Function: A nested function dfs(g, p) is defined within the sumEvenGrandparent function. This function takes two arguments: g for the grandparent node and p for the parent node. The key recursion happens within this helper function.
Base Case: Inside the dfs function, a base case checks if the parent node p is None. If it is, the function returns without performing any action. This means we have reached the end of a branch in the binary tree.
Checking Grandparent's Value: Before diving deeper into the tree, the function checks if the current grandparent node's value is even (g.val % 2 == 0). If true, and if the parent node has any children (p.left and p.right), their values are added to self.res.
Recursive Calls: The function then makes two recursive calls to continue the DFS traversal: one for the left child of the parent (dfs(p, p.left)) and one for the right child (dfs(p, p.right)). The current parent becomes the grandparent for the next level of the recursion, and its children become the new parent nodes.
Starting the Traversal: The initial calls to the dfs function start from the children of the root node since the root itself cannot be a grandchild (root's children have no grandparent and root's grandchildren are the children of root.left and root.right). Therefore, the DFS starts with dfs(root, root.left) and dfs(root, root.right) which effectively checks the trees rooted at the left and right child of the root node for eligible grandchildren.
Result: After the complete tree has been traversed, the function returns the sum stored in self.res.

By structuring the solution with recursion and maintaining state across recursive calls, the DFS algorithm effectively identifies and sums up all the nodes that fulfill the even-valued grandparent criterion. The use of a class variable to store the ongoing sum (self.res) avoids the need for passing accumulator variables through the recursive stack, simplifying the implementation.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the following binary tree structure:

In this tree:

The root node has a value of 6.
The root's children are nodes with values 3 (left child) and 5 (right child).
The grandchildren (from root) are nodes with values 2, 11 (left subtree) and 9 (right subtree).
Node 11 has children with values 13 (left child) and 5 (right child).

Now, let's apply the solution approach as described in the content:

Initialization: We initialize self.res to 0. This will hold the sum of all grandchild node values where the grandparent value is even.
DFS Function: The dfs function is ready to be invoked. It will be called with the grandparents and parents of each node.
Base Case: When dfs encounters a None node, it returns. This base case prevents the function from running indefinitely and ensures we only consider existing nodes.
Checking Grandparent's Value: As we call the dfs function, we check if the grandparent (g) node value is even. When we are at node 3 with grandparent 6, we add the values of node 3's children (2 and 11) to self.res since 6 is even. Similarly, when we are at node 5 with grandparent 6, we check node 5's child (9) and add its value to self.res.
Recursive Calls: We then recursively call dfs on node 3's children (2 and 11) and node 5's child (9), setting the current parent as the new grandparent for the next level.
Traversal: The DFS begins with dfs(6, 3) and dfs(6, 5). These calls evaluate the left and right subtrees rooted at nodes 3 and 5, respectively.
Result: We sum the values of the nodes that have even-valued grandparents throughout the traversal. The nodes that satisfy this condition in our example are 2, 11, and 9. Thus, self.res becomes 2 + 11 + 9 = 22 by the end of the traversal.

After performing these steps, the final result (self.res) holds the sum of all nodes with even-valued grandparents. In this example, the output would be 22.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val  # The value stored in the node.
5        self.left = left  # The left child of the node.
6        self.right = right  # The right child of the node.
7
8class Solution:
9    def sumEvenGrandparent(self, root: TreeNode) -> int:
10        # Initialize the total sum of values.
11        self.total_sum = 0
12
13        def dfs(grandparent, parent):
14            """
15            Depth-first search to find and add values of grandchildren with even-valued grandparents.
16
17            :param grandparent: Reference to the grandparent node.
18            :param parent: Reference to the parent node.
19            """
20            # Base case to terminate recursion if we reach a None node.
21            if parent is None:
22                return
23          
24            # If the grandparent's value is even, add the grandchildren's values.
25            if grandparent.val % 2 == 0:
26                if parent.left:
27                    self.total_sum += parent.left.val
28                if parent.right:
29                    self.total_sum += parent.right.val
30          
31            # Recur on the left and right child of the current parent node.
32            dfs(parent, parent.left)
33            dfs(parent, parent.right)
34
35        # Handle the edge case if the tree doesn't contain any nodes.
36        if root is None:
37            return 0
38
39        # Run DFS starting from the root's children to maintain the grandparent relationship.
40        dfs(root, root.left)
41        dfs(root, root.right)
42      
43        # Return the calculated total sum.
44        return self.total_sum
45

1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    // Node Constructor without children
8    TreeNode(int val) {
9        this.val = val;
10    }
11
12    // Node Constructor with children
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20public class Solution {
21    private int totalSum;
22
23    // Main method to calculate the sum of values of all nodes with even-valued grandparent
24    public int sumEvenGrandparent(TreeNode root) {
25        totalSum = 0;
26        if (root != null) {
27            // If the tree is not empty, perform depth-first search on both children
28            depthFirstSearch(null, root, root.left);
29            depthFirstSearch(null, root, root.right);
30        }
31        return totalSum;
32    }
33
34    // Helper method to perform depth-first search and accumulate the sum
35    private void depthFirstSearch(TreeNode grandparent, TreeNode parent, TreeNode current) {
36        if (current == null) {
37            // If current node is null, stop the recursion
38            return;
39        }
40      
41        // If grandparent is not null and has an even value
42        if (grandparent != null && grandparent.val % 2 == 0) {
43            // Add the value of the current node to the total sum
44            totalSum += current.val;
45        }
46
47        // Recurse for children of the current node
48        // The current parent becomes the new grandparent, and the current node becomes the parent
49        depthFirstSearch(parent, current, current.left);
50        depthFirstSearch(parent, current, current.right);
51    }
52}
53

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    // Declare a class member to store the result
15    int totalSum;
16
17    // Function to initialize the summing process for finding the total sum of all nodes
18    // with even-valued grandparents
19    int sumEvenGrandparent(TreeNode* root) {
20        // Initialize result to 0
21        totalSum = 0;
22        // Start Depth-First Search (DFS) from the children of the root node
23        if (root) {
24            dfs(root, root->left);
25            dfs(root, root->right);
26        }
27        // Return the result after traversing the whole tree
28        return totalSum;
29    }
30
31    // Depth-First Search function to traverse the tree and calculate the sum
32    void dfs(TreeNode* grandparent, TreeNode* parent) {
33        // If there is no parent node, return to stop the recursion
34        if (!parent) return;
35      
36        // Check if the grandparent's value is even.
37        // If it is, add the values of the parent's children to the result.
38        if (grandparent->val % 2 == 0) {
39            if (parent->left) totalSum += parent->left->val;
40            if (parent->right) totalSum += parent->right->val;
41        }
42      
43        // Continue the DFS for the children of the current parent node
44        dfs(parent, parent->left);
45        dfs(parent, parent->right);
46    }
47};
48

1// Define the tree node structure
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14// Variable to store the running total sum of all nodes with even-valued grandparents
15let totalSum: number;
16
17// Function to calculate the total sum of all nodes with even-valued grandparents
18function sumEvenGrandparent(root: TreeNode | null): number {
19    // Initialize the total sum to 0
20    totalSum = 0;
21
22    // Start the depth-first search if the root node exists
23    if (root) {
24        if (root.left) {
25            dfs(root, root.left); // DFS on the left child of the root
26        }
27        if (root.right) {
28            dfs(root, root.right); // DFS on the right child of the root
29        }
30    }
31
32    // Return the calculated total sum
33    return totalSum;
34}
35
36// Depth-first search function to traverse the tree
37function dfs(grandparent: TreeNode, parent: TreeNode | null): void {
38    // If the parent node does not exist, return to stop the recursion
39    if (!parent) return;
40
41    // Check if the grandparent's value is even
42    if (grandparent.val % 2 === 0) {
43        // If the grandparent's value is even, add the values of the parent's children to the total sum
44        if (parent.left) {
45            totalSum += parent.left.val;
46        }
47    
48        if (parent.right) {
49            totalSum += parent.right.val;
50        }
51    }
52
53    // Recursively continue DFS for each child of the parent node
54    if (parent.left) {
55        dfs(parent, parent.left);
56    }
57  
58    if (parent.right) {
59        dfs(parent, parent.right);
60    }
61}
62

Time and Space Complexity

Time Complexity: The time complexity of the given code is O(n) where n is the number of nodes in the binary tree. This is because the code performs a Depth-First Search (DFS) and visits each node exactly once.

Space Complexity: The space complexity of the code is O(h) where h is the height of the binary tree. This is due to the recursion stack during the DFS traversal. In the worst case (when the binary tree is skewed), the space complexity would be O(n). In the best case (when the binary tree is perfectly balanced), it would be O(log n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know