Question

In java, Write a recursive function to calculate the sum of the nodes only on even levels of the subtree. please do not add any parameters to do this function.

private int sumEvenLevels(Node current){ //you can only pass in root.

//code

}

Answer 1

Program: In this program, we calculate the sum of al nodes at the even levels of the tree recursively. Considering root to be at level zero we will be calculating the sum of all even level nodes. Class Node has definition of node, Class Solution has the function sumEvenLevels() and the main() method to test the function.

Below is the implementation:

Code:

class Node {
    int val;
    Node left, right;

    public Node(int val) {
        this.val = val;
        left = right = null;
    }
}

class Solution {

    Node root;

    // Function
    private int sumEvenLevels(Node current) {
        // Base case
        if (current == null) {
            return 0;
        }

        // Declare two child nodes
        Node child = null, child2 = null;

        // Check if current to left is null
        if (current.left != null) {
            // Assign child node to left child
            child = current.left;
        }

        // Check if child2 is null
        if (current.right != null) {

            // Assign child2 to right child
            child2 = current.right;
        }

        // Check if both child and child2 are null
        if (child != null && child2 != null) {

            // Return sum of current val and skip the next level of tree (which is odd)
            return current.val + sumEvenLevels(child.left) + sumEvenLevels(child.right)
                    + sumEvenLevels(child2.left) + sumEvenLevels(child2.right);
        }

        // Check if only child2 is null
        else if (child != null) {
            return current.val + sumEvenLevels(child.left) + sumEvenLevels(child.right);
        }

        // Check if only child is null
        else if (child2 != null) {
            return current.val + sumEvenLevels(child2.left) + sumEvenLevels(child2.right);
        }

        // Else if both are null return current node value
        else {
            return current.val;
        }
    }

    public static void main(String[] args) {

        Solution tree = new Solution();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(7);
        tree.root.left.left = new Node(2);
        tree.root.left.right = new Node(4);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(8);
        tree.root.left.left.left = new Node(13);
        tree.root.left.left.right = new Node(11);
        tree.root.right.right.right = new Node(9);
        tree.root.right.right.left = new Node(7);
        System.out.println("Sum of even level nodes: " + tree.sumEvenLevels(tree.root));

        /*
           5
        /    \
       3      7
      / \    / \
     2   4  6   8
    / \       /  \
   13  11    7    9

         */
    }
}

Output: