'Implement nodeCount() and leafCount() in a binary search tree
I am trying to implement leafCount() and nodeCount() to this recursive binary tree - program. When testing it, these two methods (or the tests of them) throw Failure, so obviously they're not working as expected. I cannot figure out where I'm doing or thinking wrong. If someone could explain what I'm doing wrong or pinpoint the problem, I would be very grateful.
public class BSTrec {
BSTNode tree, parent, curr;
public BSTrec () {
tree = null; // the root of the tree
parent = null; // keeps track of the parent of the current node
curr = null; // help pointer to find a node or its place in the tree
}
public boolean isEmpty() {
return tree == null;
}
private boolean findNodeRec(String searchKey, BSTNode subtree, BSTNode subparent) {
// recursive help method to find a node or its insertion place
if (subtree == null) { // base case 1: node not found
curr = null;
parent = subparent; // the logical parent for the value
return false;
}
else { // we are still in the tree
if (subtree.info.key.equals(searchKey)) { // base case 2: found the node
curr = subtree; // update current to point to the node
parent = subparent; // update parent to point to its parent
return true;
}
else { // must choose the right subtree to search
if (searchKey.compareTo(subtree.info.key) < 0) {
// key less than current info: search the left subtree!
return findNodeRec(searchKey, subtree.left, subtree);
}
else { // key greater than current info: search the right subtree!
return findNodeRec(searchKey, subtree.right, subtree);
}
}
}
}
public NodeInfo retrieveNode(String searchKey) {
// retrieve the info part of the node with key
// if it is in the tree
if (findNodeRec(searchKey, tree, null)) return curr.info;
else return null;
}
public void addRec(String keyIn, BSTNode subtree, BSTNode subparent, boolean goLeft) {
if (tree == null) { // a first node will be the new root: base case 1
tree = new BSTNode(new NodeInfo(keyIn));
curr = tree;
parent = null;
} // the tree was initiated, we got a new root
else { // insertion in an existing tree
if (subtree == null) { // we found the insertion place: base case 2
if (goLeft) { // the new node is to be a left child
subparent.left = new BSTNode(new NodeInfo(keyIn));
curr = subparent.left;
parent = subparent;
}
else { // the new node is to be a left child
subparent.right = new BSTNode(new NodeInfo(keyIn));
curr = subparent.right;
parent = subparent;
}
}
else { // still searching for the insertion place: left or right subtree?
if (keyIn.compareTo(subtree.info.key) < 0) {
addRec(keyIn, subtree.left, subtree, true);
// the node must be inserted in the left subtree of the
// current node: a recursive call
}
else {
addRec(keyIn, subtree.right, subtree, false);
// the node must be inserted in the right subtree of the
// current node: a recursive call
}
}
}
}
public void deleteNode(String searchKey) {
// deletes the node with the given key, uses a recursive search
boolean found = findNodeRec(searchKey, tree, null);
if (!found) // the key is not in the tree
System.out.println("The key is not in the tree!");
else { // curr points to the node to be deleted, parent to its parent
if ((curr.left == null) && (curr.right == null)) // delete a leaf
if (parent == null) // delete the last node
tree = null;
else // the leaf to be deleted is not the root
if (curr == parent.left) // delete a left child
parent.left = null;
else // delete a right child
parent.right = null;
else // delete a node with children, one or two
if ((curr.left != null) && (curr.right != null)) { // two children
BSTNode surrogateParent = curr;
BSTNode replacement = curr.left;
while (replacement.right != null) {
surrogateParent = replacement;
replacement = replacement.right;
}
// the greatest value of the left subtree is chosen as a replacement
curr.info = replacement.info; // the information is copied over
// replacement must now be deleted. It has no children, or a left child.
if (curr == surrogateParent) {
// there was no right path in the left subtree
curr.left = replacement.left; // curr "adopts" the left
// child, if any, of the replacement. The replacement is jumped over.
replacement = null;
}
else { // there was a right path in the left subtree
surrogateParent.right = replacement.left;
// replacement, the right child of its parent, is jumped over.
// The parent "adopts" its left child, if any.
replacement = null;
}
} // End: if two children
else { // delete a node with one child
if (parent == null) // delete a root with one child
if (curr.left != null) // there is a left child
tree = curr.left; // update root
else // there is a right child
tree = curr.right; // update root
// end: the node to be deleted was a root with one child
else // delete a non-root node with one child
if (curr == parent.left) // delete a left child ...
if (curr.right == null) // ... with a left child
parent.left = curr.left;
// the parent "adopts" the grandchild
else // ... with a right child
parent.left = curr.right;
// The parent "adopts" the grandchild
else // delete a right child ...
if (curr.right == null) // ... with a left child
parent.right = curr.left;
// the parent "adopts" the grandchild
else // ... with a right child
parent.right = curr.right;
// The parent "adopts" the grandchild
} // end: else a node with one child
curr = null; // curr no longer points to the deleted node
}
} // method
public void inOrder(BSTNode root) {
if (root != null) { // implicit base case: empty tree: do nothing
inOrder(root.left); // process the left subtree
System.out.println(root.info.key); // process the node itself
inOrder(root.right); // process the right subtree
}
}
public void preOrder(BSTNode root) {
if (root != null) { // implicit base case: empty tree: do nothing
System.out.println(root.info.key); // process the node itself
preOrder(root.left); // process the left subtree
preOrder(root.right); // process the right subtree
}
}
public void postOrder(BSTNode root) {
if (root != null) { // implicit base case: empty tree: do nothing
postOrder(root.left); // process the left subtree
postOrder(root.right); // process the right subtree
System.out.println(root.info.key); // process the node itself
}
}
public int nodeCount() {
int count = 0;
if (tree == null) {
count = 0;
//throw new NullPointerException();
}
else {
if (tree.left != null) {
count = 1;
count += tree.left.nodeCount();
}
if (tree.right != null) {
count = 1;
count += tree.right.nodeCount();
}
}
return count;
}
public int leafCount() {
int count = 0;
if (tree != null && tree.left == null && tree.right==null) {
return 1;
} else {
if (tree.left != null) // added check
count += tree.left.leafCount();
if (tree.right != null) // added check
count += tree.right.leafCount();
}
return count;
}
private class BSTNode {
NodeInfo info;
BSTNode left, right;
BSTNode(NodeInfo dataIn) {
info = dataIn;
left = null;
right = null;
}
public int leafCount() {
// TODO Auto-generated method stub
return 0;
}
public int nodeCount() {
// TODO Auto-generated method stub
return 0;
}
/*
BSTNode(NodeInfo dataIn, BSTNode l, BSTNode r) { // for test constructions
info = dataIn;
left = l;
right = r;
}
*/
}
}
public class NodeInfo { // so that this type can be returned String key; // add other fields as needed!
NodeInfo() {
key = null;
}
NodeInfo(String keyIn) {
key = keyIn;
}
}
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class BSTrecTest { ```
@Test
public void testLeafCount() {
BSTrec tree = new BSTrec();
assertTrue("The number of leafs should be 0", tree.leafCount() == 0);
tree.addRec("b", tree.tree, tree.parent, true);
assertTrue("The number of leafs should be 1", tree.leafCount() == 1);
tree.addRec("a", tree.tree, tree.parent, true);
tree.addRec("e", tree.tree, tree.parent, true);
tree.addRec("f", tree.tree, tree.parent, true);
tree.addRec("g", tree.tree, tree.parent, true);
assertTrue("The number of leafs should be 2", tree.leafCount() == 2);
tree.addRec("c", tree.tree, tree.parent, true);
/*
* b
* / \
* a e
* / \
* c f
* \
* g
*/
assertTrue("The number of leafs should be 3", tree.leafCount() == 3);
}
@Test
public void testNodeCount() {
BSTrec tree = new BSTrec();
assertTrue("The number of nodes should be 0", tree.nodeCount() == 0);
tree.addRec("b", tree.tree, tree.parent, true);
assertTrue("The number of nodes should be 1", tree.nodeCount() == 1);
tree.addRec("a", tree.tree, tree.parent, true);
tree.addRec("e", tree.tree, tree.parent, true);
tree.addRec("f", tree.tree, tree.parent, true);
tree.addRec("g", tree.tree, tree.parent, true);
assertTrue("The number of nodes should be 5", tree.nodeCount() == 5);
tree.addRec("c", tree.tree, tree.parent, true);
/*
* b
* / \
* a e
* / \
* c f
* \
* g
*/
assertTrue("The number of nodes should be 6", tree.nodeCount() == 6);
}
}
Solution 1:[1]
Please try to implement the two methods as your teacher asks of you:
public int leafCount() {
// TODO Auto-generated method stub
return 0;
}
public int nodeCount() {
// TODO Auto-generated method stub
return 0;
}
If you tried, and run into problems, then you can ask a question.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Adriaan Koster |