Java

Implement a method to compute the sum of keys at even depth. For example:

If the tree is empty, then the sumAtEvenDepth is 0.

If the level-order traversal of the tree is 41 21 61 11 31 51, then: 41 is at depth 0; 21 and 61 are at depth 1; 11, 31 and 51 are at depth 2. Thus, sumAtEvenDepth is 134, since there are nodes 41, 11, 31 and 51 at even depth.

Your method should run in time linear to the size of the tree. You may create a recursive helper function or use a loop. DO NOT change the class structure or function declaration.

public class BST { private static class Node { public Node(int key) { this.key = key; } private int key; private Node left; private Node right; } private Node root; // the root of the tree, null for the empty tree // TODO: implement your method here  public int sumAtEvenDepth(Node n) { ... } }