Complete the validBST() method so that it returns true if it is a leaf OR (its element is ordered properly relative to its child(ren) AND its child(ren) are also valid BST entries). If neither of those things is correct, thn the method should return false.

-----------------------------------

package edu.buffalo.cse116;

public class Entry> { /** Tree's element which is stored within this Entry. */ private E element;

/** Left child of the current Entry. */ private Entry left; /** Right child of the current Entry. */ private Entry right; /** Parent in the binary tree for the current Entry. */ private Entry parent;

/** * Creates a new BSTEntry object with the specified element and parent BSTEntry. * * @param element Data to be held in this BSTEntry. * @param parent Parent for this entry within the binary tree. */ public Entry(E element, Entry parent) { this.element = element; this.parent = parent; }

/** * Validates whether the this Entry is ordered legally with respect to its child(ren) AND if any children are also * legal. It might still be possible for the BST rooted at this Entry to not be perfectly legal, but this does a good * enough job while making certain students understand how BSTs work. * * @return True if this Entry is a leaf OR (its element is ordered properly with respect to its child(ren) AND its * child(ren) are also valid BST entries; false if this Entry or any descendant is not legally ordered. */ public boolean validBSTEntry() { } }

---------------------------------

test

package edu.buffalo.cse116;

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail;

import java.lang.reflect.Field;

import org.junit.Before; import org.junit.Test;

public class EntryTest {

@Test public void testValidBSTNoChildren() { assertTrue("Subtree with only a root node must be valid!", nodes[9].validBSTEntry()); }

@Test public void testValidBSTLeftChildLarger() { assertFalse("Subtree where left child is larger is not valid!", nodes[4].validBSTEntry()); }

@Test public void testValidBSTLeftChildEqual() throws Exception { String elem = getElement(nodes[4]); setElement(nodes[10], elem); assertTrue("Subtree where left child is equal should be valid!", nodes[4].validBSTEntry()); }

@Test public void testValidBSTLeftChildSmaller() throws Exception { setElement(nodes[10], "096"); assertTrue("Subtree where left child is smaller should be valid!", nodes[4].validBSTEntry()); }

@Test public void testValidBSTRightChildSmaller() throws Exception { setElement(nodes[9], "c"); assertFalse("Subtree where right child is smaller is not valid!", nodes[8].validBSTEntry()); }

@Test public void testValidBSTRightChildEqual() throws Exception { String elem = getElement(nodes[8]); setElement(nodes[9], elem); assertTrue("Subtree where left child is equal should be valid!", nodes[8].validBSTEntry()); }

@Test public void testValidBSTRightChildLarger() { assertTrue("Subtree where left child is smaller should be valid!", nodes[8].validBSTEntry()); }

@Test public void testValidBSTBothChildrenValid() throws Exception { setElement(nodes[1], "k"); assertTrue("Subtree where left child is smaller and right child is equal should be valid!", nodes[2].validBSTEntry()); }

@Test public void testValidBSTLeftChildInvalidRightChildValid() throws Exception { setElement(nodes[1], "c"); setElement(nodes[0], "F"); assertTrue("Subtree where left child is larger and right child is equal should be valid!", nodes[2].validBSTEntry()); }

@Test public void testValidBSTLeftChildValidRightInvalid() throws Exception { assertFalse("Subtree where left child is smaller and right child is smaller should not be valid!", nodes[2].validBSTEntry()); }

@Test public void testValidBSTChildrenValidGrandchildInvalid() throws Exception { setElement(nodes[4], "i"); assertFalse("Subtree where both child are correct, but a grandkid is incorrect should not be valid!", nodes[5].validBSTEntry()); }

@Test public void testValidBSTChildInvalidGrandchildrenValid() throws Exception { setLeft(nodes[4], null); setElement(nodes[6], "b"); setElement(nodes[1], "g"); setElement(nodes[4], "x"); assertFalse("Subtree where a child is not correct should not be valid (even if the grandkids are correct)!", nodes[6].validBSTEntry()); }

@Test public void testValidBSTChildValidGrandchildrenValidGreatGrandchildInvalid() throws Exception { setElement(nodes[6], "h"); setElement(nodes[1], "g"); setElement(nodes[4], "j"); assertFalse("Subtree where a single great-grandchild is not correct should not be valid!", nodes[6].validBSTEntry()); }

@Test public void testValidBSTChildComplexValid() throws Exception { setElement(nodes[1], "c"); setElement(nodes[2], "b"); setElement(nodes[3], "e"); setElement(nodes[4], "h"); setElement(nodes[6], "d"); setElement(nodes[7], "i"); setElement(nodes[8], "j"); setElement(nodes[9], "k"); setElement(nodes[10], "g"); assertTrue("Subtree where everything is correct should be valid!", nodes[7].validBSTEntry()); }

private Entry[] nodes; private Field elementField; private Field leftField; private Field rightField; private Field parentField;

@SuppressWarnings("unchecked") @Before public void setUp() throws Exception { Class bstEntryKlass = Entry.class; assertEquals("Your BSTEntry class does not need any additional fields!", 4, bstEntryKlass.getDeclaredFields().length); try { elementField = bstEntryKlass.getDeclaredField("element"); elementField.setAccessible(true); } catch (Exception e) { fail("Your BSTEntry class must preserve the \"element\" field!"); } try { leftField = bstEntryKlass.getDeclaredField("left"); leftField.setAccessible(true); } catch (Exception e) { fail("Your BSTEntry class must preserve the \"left\" field!"); } try { rightField = bstEntryKlass.getDeclaredField("right"); rightField.setAccessible(true); } catch (Exception e) { fail("Your BSTEntry class must preserve the \"right\" field!"); } try { parentField = bstEntryKlass.getDeclaredField("parent"); parentField.setAccessible(true); } catch (Exception e) { fail("Your BSTEntry class must preserve the \"parent\" field!"); } nodes = new Entry[11]; for (int i = 0; i < nodes.length; i++ ) { nodes[i] = new Entry<>(Character.toString((char) ('a' + i)), null); }

// Setup the left and right children in the tree setLeft(nodes[5], nodes[3]); setRight(nodes[5], nodes[4]);

setLeft(nodes[4], nodes[10]);

setLeft(nodes[2], nodes[0]); setRight(nodes[2], nodes[1]);

setLeft(nodes[6], nodes[2]); setRight(nodes[6], nodes[5]);

setRight(nodes[8], nodes[9]);

setLeft(nodes[7], nodes[6]); setRight(nodes[7], nodes[8]);

// Setup the parents in the tree setParent(nodes[6], nodes[7]); setParent(nodes[8], nodes[7]); setParent(nodes[9], nodes[8]); setParent(nodes[5], nodes[6]); setParent(nodes[2], nodes[6]); setParent(nodes[0], nodes[2]); setParent(nodes[1], nodes[2]); setParent(nodes[10], nodes[4]); setParent(nodes[3], nodes[5]); setParent(nodes[4], nodes[5]);

}

public String getElement(Entry node) throws IllegalArgumentException, IllegalAccessException { return (String) elementField.get(node); }

public void setElement(Entry node, String elem) throws IllegalArgumentException, IllegalAccessException { elementField.set(node, elem); }

public void setLeft(Entry node, Entry newLeft) throws IllegalArgumentException, IllegalAccessException { leftField.set(node, newLeft); }

public void setRight(Entry node, Entry newRight) throws IllegalArgumentException, IllegalAccessException { rightField.set(node, newRight); }

public void setParent(Entry node, Entry newParent) throws IllegalArgumentException, IllegalAccessException { parentField.set(node, newParent); } }