7.13 LAB: BST validity checker

Step 1: Inspect the Node.java file

Inspect the class declaration for a BST node in Node.java. Access Node.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. Each node has a key, a left child reference, and a right child reference.

Step 2: Implement the BSTChecker.checkBSTValidity() method

Implement the checkBSTValidity() method in the BSTChecker class in the BSTChecker.java file. The method takes the tree's root node as a parameter and returns the node that violates BST requirements, or null if the tree is a valid BST.

A violating node will be one of three things:

• A node in the left subtree of an ancestor with a lesser key
• A node in the right subtree of an ancestor with a greater key
• A node with the left or right field referencing an ancestor

Note: Other types of BST violations can occur, but are not covered in this lab.

The given code in LabProgram.java reads and parses input, and builds the tree for you. Nodes are presented in the form (key, leftChild, rightChild), where leftChild and rightChild can be nested nodes or "None". A leaf node is of the form (key). After parsing tree input, the BSTChecker.checkBSTValidity() method is called and the returned node's key, or "No violation", is printed.

Ex:

If the input is:

(50, (25, None, (60)), (75))

which corresponds to the tree above, then the output is:

60

because 60 violates BST requirements by being in the left subtree of 50.

Ex:

If the input is:

(20, (10), (30, (29), (31)))

which corresponds to the tree above, then the output is:

No violation

because all BST requirements are met.

The input format doesn't allow creating a tree with a node's child referencing an ancestor, so unit tests are used to test such cases.

LabProgram.java

import java.util.*;

public class LabProgram { public static void main(String[] args) { // Get user input Scanner reader = new Scanner(System.in); String userInput = reader.nextLine();

// Parse into a binary tree Node userRoot = Node.parse(userInput); if (userRoot != null) { Node badNode = BSTChecker.checkBSTValidity(userRoot); if (badNode != null) { System.out.print(String.valueOf(badNode.key)); System.out.print(" "); } else { System.out.print("No violation"); System.out.print(" "); } } else { System.out.print("Failed to parse input tree"); System.out.print(" "); } reader.close(); } }

Node.java

import java.util.*;

public class Node { private static String removeLeadingWhitespace(String str) { int i = 0; while (i < (int) str.length()) { // If the character at index i is not whitespace, then return the // substring that starts at i if (!Character.isWhitespace(str.charAt(i))) { return str.substring(i); }

i++; }

// Completing the loop means the entire string is whitespace return new String(); }

public int key; public Node left; public Node right;

public Node(int nodeKey, Node leftChild) { this(nodeKey, leftChild, null); }

public Node(int nodeKey) { this(nodeKey, null, null); }

public Node(int nodeKey, Node leftChild, Node rightChild) { key = nodeKey; left = leftChild; right = rightChild; }

public void close() { }

// Counts the number of nodes in this tree public int count() { int leftCount = 0; if (left != null) { leftCount = left.count(); } int rightCount = 0; if (right != null) { rightCount = right.count(); } return 1 + leftCount + rightCount; }

// Inserts the new node into the tree. public void insert(Node node) { Node currentNode = this; while (currentNode != null) { if (node.key < currentNode.key) { if (currentNode.left != null) { currentNode = currentNode.left; } else { currentNode.left = node; currentNode = null; } } else { if (currentNode.right != null) { currentNode = currentNode.right; } else { currentNode.right = node; currentNode = null; } } } }

public void insertAll(final ArrayList keys) { for (int key : keys) { insert(new Node(key)); } }

public static Node parse(String treeString) { // A node is enclosed in parentheses with a either just a key: (key), // or a key, left child, and right child triplet: (key, left, right). The // left and right children, if present, can be either a nested node or // "null".

// Remove leading whitespace first treeString = Node.removeLeadingWhitespace(treeString);

// The string must be non-empty, start with "(", and end with ")" if (0 == treeString.length() || treeString.charAt(0) != '(' || treeString.charAt(treeString.length() - 1) != ')') { return null; }

// Parse between parentheses treeString = treeString.substring(1, treeString.length() - 1);

// Find non-nested commas ArrayList commaIndices = new ArrayList(); int parenCounter = 0; for (int i = 0; i < (int) treeString.length(); i++) { char character = treeString.charAt(i); if ('(' == character) { parenCounter++; } else if (')' == character) { parenCounter--; } else if (',' == character && 0 == parenCounter) { commaIndices.add(i); } }

// If no commas, treeString is expected to be just the node's key if (0 == commaIndices.size()) { return new Node(Integer.parseInt(treeString)); }

// If number of commas is not 2, then the string's format is invalid if (2 != commaIndices.size()) { return null; }

// "Split" on comma int i1 = commaIndices.get(0); int i2 = commaIndices.get(1); String piece1 = treeString.substring(0, i1); String piece2 = treeString.substring(i1 + 1, i2); String piece3 = treeString.substring(i2 + 1);

// Make the node with just the key Node nodeToReturn = new Node(Integer.parseInt(piece1));

// Recursively parse children nodeToReturn.left = Node.parse(piece2); nodeToReturn.right = Node.parse(piece3); return nodeToReturn; } }

BSTChecker.java

import java.util.*;

public class BSTChecker { public static Node checkBSTValidity(Node rootNode) { // Your code here (remove the placeholder line below) return rootNode; } }