In Eclipse.

Node

public class Node , Value> {

Key key; // key

Value val; // associated value

Node left, right; // links to subtrees

int n; // # nodes in subtree rooted here

public Node(Key key, Value val, int n) {

this.key = key;

this.val = val;

this.n = n;

}

/**

* @param node root of the sub-tree

* @return true if for each node in the sub-tree, n field value matches the number of nodes in its sub-tree, otherwise false

*/

public static , Value> boolean isBinaryTree(Node node) {

// provide your implementation here

throw new UnsupportedOperationException("Not implemented yet");

}

}

Node test.

import org.junit.Assert;

import org.junit.jupiter.api.Test;

class NodeTest {

@Test

void testIsBinaryTree_1() {

Node node = null;

Assert.assertTrue(Node.isBinaryTree(node));

}

@Test

void testIsBinaryTree_2() {

Node node = null;

node = new Node(1, "Fall", 0);

Assert.assertFalse(Node.isBinaryTree(node));

node = new Node(1, "Fall", 2);

Assert.assertFalse(Node.isBinaryTree(node));

node = new Node(1, "Fall", 1);

Assert.assertTrue(Node.isBinaryTree(node));

}

@Test

void testIsBinaryTree_3() {

Character[] keys = {'S', 'E', 'X', 'A', 'R', 'C', 'H', 'M'};

Node root = null;

for (int i=0; i

root = put(root, keys[i], i);

}

Assert.assertTrue(Node.isBinaryTree(root));

updateN(root, 'R', 2);

Assert.assertFalse(Node.isBinaryTree(root));

updateN(root, 'R', 4);

Assert.assertFalse(Node.isBinaryTree(root));

}

@Test

void testIsBinaryTree_4() {

Character[] keys = {'S', 'E', 'X', 'A', 'R', 'C', 'H', 'M', 'Z', 'Y'};

Node root = null;

for (int i=0; i

root = put(root, keys[i], i);

}

Assert.assertTrue(Node.isBinaryTree(root));

updateN(root, 'S', 11);

Assert.assertFalse(Node.isBinaryTree(root));

updateN(root, 'S', 12);

Assert.assertFalse(Node.isBinaryTree(root));

}

private static , Value> Node put(Node node, Key key, Value val) {

if (node == null)

return new Node(key, val, 1);

int cmp = key.compareTo(node.key);

if (cmp

node.left = put(node.left, key, val);

else if (cmp > 0)

node.right = put(node.right, key, val);

else

node.val = val;

node.n = size(node.left) + size(node.right) + 1;

return node;

}

private static , Value> void updateN(Node node, Key key, int n) {

if (node == null) return;

int cmp = key.compareTo(node.key);

if (cmp

updateN(node.left, key, n);

else if (cmp > 0)

updateN(node.right, key, n);

else

node.n = n;

}

private static , Value> int size(Node node) {

return node==null? 0: node.n;

}

}

Write a recursive method isBinaryTreeO that takes a Node as argument and returns true if the subtree count field n is consistent in the data structure rooted at that node, false otherwise. |