Issues with correctly linking the child to the parent node and linking it back to its ancestor?

[Peta Brady]

Greetings,

I am having issues with correctly linking the child to the parent node and linking it back to its ancestor. Here is a copy of the code that I submitted for reference:

import java.util.*;

public class BSTChecker {
	
	public static Node checkBSTValidity(Node rootNode) {
		// Your code here (remove the placeholder line below)
		 return checkBSTValidityHelper(rootNode, Integer.MIN_VALUE, Integer.MAX_VALUE, new HashSet<>());
	}
	
	
	private static Node checkBSTValidityHelper(Node node, int min, int max, Set<Node> ancestors) {
	   
		 if (node == null) {  
		     return null;
		 }
		 
		 if (node.key <= min || node.key >= max){
		     return node;
		 }
		 
		 if (ancestors.contains(node)) {
		     return node;
		 }
		 
		 ancestors.add(node);
		 
		 if (node.left != null) {
		     if (node.left == node) {
		         return node.left;
		     }
		 
		     Node leftViolation = checkBSTValidityHelper(node.left, min, node.key, ancestors);
		     if (leftViolation != null) {
		         return leftViolation;
		     }
	    }
	
	    if (node.right != null) {
	        if (node.right == node) {
	            return node.right;
	        }
	   
		     Node rightViolation = checkBSTValidityHelper(node.right, node.key, max, ancestors);
		     if (rightViolation != null) {
		         return rightViolation;
		 }
	  }	 
		 
	  ancestors.remove(node);
	
	  return null;
	}
}

Also, here are the error messages and feedback that I received:

1. Invalid tree with right child linking to ancestor with this feedback: checkBSTValidity() returned a node that is not the BST rule-violating node. The node was either the left or right child pointing to an ancestor must be returned.

2. Invalid tree with left child linking to parent with this feedback: checkBSTValidity() returned a node that is not the BST rule-violating node.

3. Invalid tree with left child linking to ancestor with this feedback: checkBSTValidity() returned a node that is not the BST rule-violating node.



Please let me know if anything else is needed. Thank you-

[Piet Souris]

hi Peta,

can you give us the code for the Node-class as well?

[Tim Holloway]

Piet Souris wrote:hi Peta,

can you give us the code for the Node-class as well?

Yeah. Node should have a property named "parent" or something like that.

[Norm Radder]

 here are the error messages and feedback that I received:

Where do those error messages come from?

[Peta Brady]

Thanks for the reply. Here is a copy of the read-only code for the Node.java file:

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<Integer> 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<Integer> commaIndices = new ArrayList<Integer>();
		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;
	}
}

Also, here is a copy of the ready-only LabProgram,java code; in case anyone requests it for reference.

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("\n");
			} 
			else {
				System.out.print("No violation");
				System.out.print("\n");
			}
		} 
		else {
			System.out.print("Failed to parse input tree");
			System.out.print("\n");
		}
      
      reader.close();
	}
}

[Peta Brady]

My apologies, the error messages come from the IDE and here is a copy of the Node.java and LabProgram.java in its proper format. Both files are read-only. Thank you-

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<Integer> 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<Integer> commaIndices = new ArrayList<Integer>();
		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;
	}
}

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("\n");
			} 
			else {
				System.out.print("No violation");
				System.out.print("\n");
			}
		} 
		else {
			System.out.print("Failed to parse input tree");
			System.out.print("\n");
		}
      
      reader.close();
	}
}

[Tim Holloway]

Based on that, Node is intended for a doubly-linked list. To form a tree, you'd need a parent-node pointer and no such property exists for that class. So you're out of luck.

You could subclass your Node class and put a parent property in it, but Node by itself isn't designed for that.

[Carey Brown]

It's not clear to me why you need a list of ancestors to validate a tree. Simply walking the tree recursively and comparing the current key with the left and right keys should be sufficient. Am I missing something?

[Norm Radder]

Can you post the input string for running the program?

What program generated the messages?  

[Norm Radder]

having issues with correctly linking the child to the parent node and linking it back to its ancestor.

Where in your code are you doing any linking of nodes?  The only places I see that being done is in the Read-Only code which I assume was provided by your instructor.

Do you have a description of what your code is supposed to do?

[Peta Brady]

Thanks for the reply. Yes, I am working on a lab assignment. I made some adjustments and now have two errors. Here is a copy of the assignment, the code that I modified, and errors listed below:

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 X will meet one or more of the following conditions:

   X is in the left subtree of ancestor Y, but X's key is > Y's key
   X is in the right subtree of ancestor Y, but X's key is < Y's key
   X's left or right child references 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:
Tree 1 with 60 node violation

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:
Tree 1 with 60 node violation

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.

import java.util.*;

public class BSTChecker {
	
	public static Node checkBSTValidity(Node rootNode) {
		// Your code here (remove the placeholder line below)
		 Node loopViolation = detectLoopViolation(rootNode);
		 if (loopViolation != null) {
		     return loopViolation;
	    }
	
	
	    return checkKeyViolations(rootNode);
	}
	
	
	private static Node detectLoopViolation(Node rootNode) {
	   
		 Stack<Node> nodes = new Stack<Node>();
		 nodes.push(rootNode);
		 
		 
		 HashSet<Node> distinctSet = new HashSet<Node>();
	    while (!nodes.isEmpty()) {
	        Node node = nodes.pop();
	        
		
		 if (node!= null) {  
		     
		     if (distinctSet.contains(node.left) || distinctSet.contains(node.right)) {
		         return node;
		     }
		 
		     distinctSet.add(node);
		     
		     
		     nodes.push(node.left);
		     nodes.push(node.right);
		   }
     	}    
	    
	   return null;
	}
	
	
	private static Node checkKeyViolations(Node rootNode) {
	   Stack<Node> nodes = new Stack<>();
	   nodes.push(rootNode);
	   
	   while (!nodes.isEmpty()) {
	       Node node = nodes.pop();
	       if (node != null) {
	          
	           Node badnode = findViolator(node.left, node, "Left");
	           if (badNode != null) {
	               return badNode;
	
	           }
	           
	           badNode = findViolator(node.right, node, "Right");
	           if (badNode != null) {
	               return badNode;
	           }
	           
	           nodes.push(node.left);
	           nodes.push(node.right);
	           
	           
	       }
	   }  
	       
		
		return null;
	}
	
	
	private static Node findViolator(Node child, Node parent, String direction) {
	    if (child == null) {
	        return null;
	    }
	    
       
       if ("Left". equals(direction) && child.key >= parent.key) {
           return child; 
       else if ("Right". equals(direction) && child.key <= parent.key) {
          return child;
       }
      
	    return null;
	}
}

BSTChecker.java:85: error: 'else' without 'if'
      else if ("Right". equals(direction) && child.key <= parent.key) {
      ^
BSTChecker.java:91: error: reached end of file while parsing
}
^
2 errors

[Campbell Ritchie]

Those compiler errors have to do with the placement of {...}.

[Piet Souris]

hi Peta,

did you manage to get a correct parsing of the inputstring, and a correct check of the validity of the tree?

The validity checking does not need much knowledge of ancestors, though. For instance, say we have this tree
                       5
                 /                \
           3                       8
      /     \                   /        \
  1          4               6         10
/  \                           \
0    2                          7

if you look at the left node 6, then you see its key must be larger than the ancestor of its ancestor, but smaller than its ancestor. Likewise, for the rightnode 4, it must be larger than its ancestor, but smaller that the ancestors ancestor.

So you will soon start to think of the methods

private static boolean isValidLeftNode(Node node, int min, int max) {...}
private static boolean isValidRightNode(Node node, int min, int max) {...}

and you can check the validity with something like:

public static boolean isValidTree(Node node) {
        return isValidLeftNode(node.left, Integer.MIN_VALUE, node.key) &&
               isValidRightNode(node.right, node.key, Integer.MAX_VALUE)
        ;
}

and remember that a null node is always valid.

[Peta Brady]

Thanks to everyone for sharing their insight and efforts to assist me as I learn Java. I did manage to fix the compiler errors. Based on the great recommendations, I made some adjustments and submitted the following code:

import java.util.*;

public class BSTChecker {

    public static Node checkBSTValidity(Node rootNode) {
        if (rootNode == null) {
            return null;
        }

        Node loopViolation = detectLoopViolation(rootNode);
        if (loopViolation != null) {
            return loopViolation;
        }

        Node valueViolation = validateSubtree(rootNode, Integer.MIN_VALUE, Integer.MAX_VALUE);
        if (valueViolation != null) {
            return valueViolation;
        }

        return null;
    }

    private static Node detectLoopViolation(Node rootNode) {
        Stack<Node> nodes = new Stack<>();
        nodes.push(rootNode);

        HashSet<Node> visitedNodes = new HashSet<>();
        while (!nodes.isEmpty()) {
            Node node = nodes.pop();

            if (node != null) {
                if (visitedNodes.contains(node.left) || visitedNodes.contains(node.right)) {
                    return node;
                }

                visitedNodes.add(node);
                nodes.push(node.left);
                nodes.push(node.right);
            }
        }

        return null;
    }

    private static Node validateSubtree(Node node, int min, int max) {
        if (node == null) {
            return null;
        }

        if (node.key <= min || node.key >= max) {
            return node;
        }

        Node leftViolation = validateSubtree(node.left, min, node.key);
        if (leftViolation != null) {
            return leftViolation;
        }

        Node rightViolation = validateSubtree(node.right, node.key, max);
        if (rightViolation != null) {
            return rightViolation;
        }

        return null;
    }
}

I ran the code through IntelliJ IDEA, but the IDE in the lab is different so I am learning how to inspect the file and fix the mistakes.  It has been cumbersome, but I feel like it is helping me avoid "the loop"