1315. Sum of Nodes with Even-Valued Grandparent
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 thesumEvenGrandparent
function. This function takes two arguments:g
for the grandparent node andp
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 nodep
isNone
. 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
andp.right
), their values are added toself.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 ofroot.left
androot.right
). Therefore, the DFS starts withdfs(root, root.left)
anddfs(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 EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following binary tree structure:
1 6 2 / \ 3 3 5 4 / \ \ 5 2 11 9 6 / \ 7 13 5
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
to0
. 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 aNone
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) toself.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 toself.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)
anddfs(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.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.