Java 101 Chapter 14

1315. Sum of Nodes with Even-Valued Grandparent

The following exercise comes from leetcode and it is useful for practicing:

• recursion
• Binary Trees
• DFS

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:

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.

Solution:

My solution is quite simple, I used an elegant solution using recursion and gets the job done in a couple lines.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return getEvenSum(root, null, null);
    }
    public int getEvenSum(TreeNode node,TreeNode parent, TreeNode grandparent){
        if(node != null){
            int sum=0;
            if(grandparent != null && grandparent.val%2 ==0 ){
                sum += node.val;
            }
            return sum + getEvenSum(node.left,node,parent) + getEvenSum(node.right,node,parent)  ;
        }
        return 0;
    }
}

Also, I decided to go further in this problem so I decided to solve it iterative too. Using a different approach. Now, we get the value of the grandsons nodes and add that into the sum. this solution takes O(N) in both memory and execution time, but it is way more friendly with the stack space.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode parent=null,grand=null;
        q.add(root);
        int sum=0;
        while(q.size() >0){
            int nodesPerLevel= q.size();
            while(nodesPerLevel-- > 0){
                TreeNode tmp = q.poll();
                if(tmp.val %2 ==0 ) sum =sum+ getGrandsonsSum(tmp);
                if(tmp.left != null) q.add(tmp.left);
                if(tmp.right != null) q.add(tmp.right);
            }
            
        }
        
        return sum;        
    }
    public int getGrandsonsSum(TreeNode node){
        int sum=0;
        if(node.left != null){
            if(node.left.left !=null )sum += node.left.left.val;
            if(node.left.right !=null )sum += node.left.right.val;
        }
        if(node.right != null){
            if( node.right.left  !=null ) sum += node.right.left.val;
            if( node.right.right !=null ) sum += node.right.right.val;
        }
        return sum;
    }
}