Sum of Nodes With Even Valued Grandparent Solution
Leetcode Solution: Understand Leetcode problem Sum of Nodes With Even Valued Grandparent(1315) Solution
In this article we’ll be solving the problem: Sum of Nodes with Even-Valued Grandparent. Just like the problem, Deepest Leaves Sum and Leaf Similar Trees, this problem also requires a change in the simple pre order Tree Traversal.
Given a binary tree, return the sum of values of nodes with even-valued grandparent.
(A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0.
Example 1:
6
/ \
7 8
/ \ / \
2 7 1 3
/ / \ \
9 1 4 5
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.
Constraints:
The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.
To solve this problem we’ve to find the sum of all the nodes whose grand parents have even values. Now, in the simple pre order tree traversal, the node does not have the access to its parent or grand parents, so, we’ll have to update the pre order tree traversal by passing the parent and the grand parents in the tree traversal recursions. Here is the program for a simple pre order tree traversal:
func preOrder(node *TreeNode) {
if node == nil {
return nil
}
fmt.Println(node.Val)
preOrder(node.Left)
preOrder(node.Right)
}
The node variable cannot access its parent here. But if we pass the parent, and the grand parent in the pre order
function then the node can access them, for example:
func preOrder(node, parent, grandParent *TreeNode) {
if node == nil {
return nil
}
fmt.Println(node.Val)
if parent != nil {
// in case of root parent will be nil
fmt.Println(parent.Val)
}
if grandParent != nil {
// for the direct children of root the grandParent will be nil
fmt.Println(grandParent.Val)
}
// for node's left and the right child the node's parent become the grand parent
preOrder(node.Left, node, parent)
preOrder(node.Right, node, parent)
}
Here, we’re passing the parent and the grand parent to the preOrder function and this way it is becoming available for
each of the nodes.
As we’ve looked into how to access the grand parent for a node we can then proceed to solve the current problem.
In this(^) image the color for the nodes match with their grand parent. The nodes in red will be ignored as the grand parent has an odd value.
Here is the program for that:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func sumEvenGrandparent(root *TreeNode) int {
var sum int
if root == nil {
return 0
}
sum = 0
preOrder(root, nil, nil, &sum)
return sum
}
func preOrder(node, parent, grandParent *TreeNode, sum *int) {
if grandParent != nil && grandParent.Val % 2 == 0 {
*sum += node.Val
}
if node.Left != nil {
preOrder(node.Left, node, parent, sum)
}
if node.Right != nil {
preOrder(node.Right, node, parent, sum)
}
}
The logic remains same to what we’ve discussed earlier. The new portion in program code is a check to find if the grand parent has an even value. This program can be found on GitHub as well.
