# Help with my Binary tree. (Node links are incorrect) Please!

Printable View

• April 18th, 2013, 11:31 AM
Jacksla3
Help with my Binary tree. (Node links are incorrect) Please!
Hey everyone. I desperately need a second set of eyes to look at my code for this binary tree I've been working on. I originally had it functioning great as a binary search tree, yet my professor is stressing that having the tree sorted isn't important only keeping it balanced when input is added to the tree. I'm getting nullPointerExceptions, or nodes other than the root aren't being added to the tree properly. I think I'm linking the nodes to the tree incorrectly. I've been at this for days and my brain feels like mush, I suspect it's something simple for you guys to understand. Any help would be more than appreciated. The binary tree contains nodes with String objects in them, frequency (for duplicate entries), and links to 2 child nodes. Search and frequency was working perfectly and somehow I screwed it up along with the insertion of new nodes when I focused on balancing it.

Node Class:
Code Java:

``` public class Node {   String item; // The data in this node. Node left; // Pointer to left subtree. Node right; // Pointer to right subtree. int freq = 1; Node(String str) { // Constructor. Make a node containing the specified string. // Note that left and right pointers are initially null. item = str; } } // end nested class TreeNode     //Driver Class: import java.io.*; import java.util.Scanner;   public class Driver{   public static void main(String[] args) { BinaryTree tree = new BinaryTree(null); Scanner input = new Scanner(System.in); int select = 0; System.out.println("Welcome to the Binary Search Tree program."); select = tree.menuStart();   while (select != 4) { // Get one string from the user, insert it into the tree, // and print some information about the tree. Exit if the // user enters an empty string. Note that all strings are // converted to lower case.   // TextIO.putln("\n\nEnter a string to be inserted, or press return to end."); // TextIO.put("? ");   while(select == 1){     System.out.print("Enter new string: "); String item; // The user's input. item = input.nextLine(); if (item.length() == 0) System.out.println("Invalid input, please enter a string."); if (tree.treeContains(tree.root,item)) { // Don't insert a second copy of an item that is already // in the tree. System.out.println(item + " is already in the tree. It's frequency is now: " + tree.treeInsertFrequency(tree.root, item)); } else { tree.treeInsert(item, tree.root); // Add user's string to the tree. } System.out.println("Please enter a new command: "); select = tree.menuStart(); }     while(select == 2) { System.out.println("Please enter the string to search for: "); String item = input.nextLine(); if (item.length() == 0) System.out.println("Invalid search input, please enter a string."); tree.Show(); if (tree.treeContains(tree.root,item)) {   System.out.println(item + " exists in the tree. It's frequency is " + tree.treeFrequency(tree.root, item)); } else System.out.println("String does not exist in the Binary Tree."); select = tree.menuStart(); }   while(select == 3){     System.out.println("The tree contains " + tree.countNodes(tree.root) + " unique strings."); System.out.println("Contents of tree:"); tree.preOrderList(tree.root); select = tree.menuStart();} } // end while }}     //Finally the problem, the BinaryTree class:   import java.io.*; import java.util.Scanner;   public class BinaryTree{   public static int size =1; public static Node root = new Node(null); public BinaryTree(String str){ String initStr = str; }   static int menuStart(){ Scanner input = new Scanner(System.in); System.out.println("Enter one of the following numbers to use the tree:"); System.out.println("1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program."); int temp = 0;   temp = input.nextInt();   while(temp!=1 && temp!=2 && temp!=3 && temp!=4){ System.out.println("Invalid command, choose a number 1-4 please."); temp = input.nextInt(); }   return temp; }     public static void treeInsert(String newItem, Node r) { String it = newItem; if(r == null){ r = new Node(newItem);} else{ System.out.println(treeBalance(r)); System.out.println(r); if(r == null){ r = new Node(it); System.out.println(r.item);} else{ if(treeBalance(r) == true) treeInsert(newItem, r.left); else treeInsert(newItem, r.right);} } }   public static void Show(){ System.out.println(root.item); }   public static void setNode(String it, Node sr){   if(sr == null){ sr = new Node(it);} else{ if(treeBalance(sr) == true) sr = sr.left; else sr = sr.right; setNode(it, sr); } }   static boolean treeBalance(Node b){ if((countNodes(b.left) == countNodes(b.right)) || (countNodes(b.left) < countNodes(b.right) )) return true; else return false;}     /** * Return true if item is one of the items in the binary * sort tree to which root points. Return false if not. */ static boolean treeContains( Node root, String item ) { if ( root == null ) { // Tree is empty, so it certainly doesn't contain item. return false; } else if ( item.equals(root.item) ) { // Yes, the item has been found in the root node. return true; } else if ( item != null) { // If the item occurs, it must be in the left subtree. return treeContains( root.left, item ); } else { // If the item occurs, it must be in the right subtree. return treeContains( root.right, item ); } } // end treeContains()   static int treeInsertFrequency( Node rf, String item ) { if ( rf == null ) { // Tree is empty, so it certainly doesn't contain item. return 0; } else if ( item.equals(rf.item) ) { // Yes, the item has been found in the rf node. rf.freq++; return rf.freq; } else if ( item.compareTo(rf.item) < 0 ) { // If the item occurs, it must be in the left subtree.   return treeInsertFrequency( rf.left, item ); } else { // If the item occurs, it must be in the right subtree.   return treeInsertFrequency( rf.right, item ); } }   static int treeFrequency( Node f, String item ) { if ( f == null ) { // Tree is empty, so it certainly doesn't contain item. return 0; } else if ( item.equals(f.item) ) { // Yes, the item has been found in the f node.   return f.freq; } else if ( item.compareTo(f.item) < 0 ) { // If the item occurs, it must be in the left subtree.   return treeFrequency( f.left, item ); } else { // If the item occurs, it must be in the right subtree.   return treeFrequency( f.right, item ); } }   static boolean rootExists(){ if(root == null){ return false; } else return true; }   public static void preOrderList(Node node) {   if ( node != null ) { System.out.println(node.item + " "); preOrderList(node.left); // Print items in l subtree. // Print item in the node. preOrderList(node.right); // Print items in the r subtree. } } // end preOrderList() /** * Count the nodes in the binary tree. * @param node A pointer to the root of the tree. A null value indicates * an empty tree * @return the number of nodes in the tree to which node points. For an * empty tree, the value is zero. */ public static int countNodes(Node node) { if ( node == null ) { // Tree is empty, so it contains no nodes. return 0; } else { // Add up the root node and the nodes in its two subtrees. int leftCount = countNodes( node.left ); int rightCount = countNodes( node.right ); return 1 + leftCount + rightCount; } } } // end countNodes()```
• April 18th, 2013, 11:42 AM
Norm
Re: Help with my Binary tree. (Node links are incorrect) Please!
Quote:

I'm getting nullPointerExceptions
What variable is null? Why doesn't the code test for the null value before it gets the exception?

One problem I see is too much use of static variables and methods.
• April 18th, 2013, 12:04 PM
Jacksla3
Re: Help with my Binary tree. (Node links are incorrect) Please!
I know where the nullPointerException is occurring, BinaryTree line 83 i think. It's a logic error I think, I think I may be creating a separate tree somehow by accident so when the root tree is accessed the nodes aren't there (?). The main piece of code I've been struggling with is this: (Also, the setNode method was an idea I was toying with it isn't being used at the moment because I can't even get the root.left and root.right to appear) Thank you for your help!

Code java:

```public static void treeInsert(String newItem, Node r) { String it = newItem; if(r == null){ r = new Node(newItem);} else{ System.out.println(treeBalance(r)); System.out.println(r); if(r == null){ r = new Node(it); System.out.println(r.item);} else{ if(treeBalance(r) == true) treeInsert(newItem, r.left); else treeInsert(newItem, r.right);} } }   public static void Show(){ System.out.println(root.item); }   public static void setNode(String it, Node sr){   if(sr == null){ sr = new Node(it);} else{ if(treeBalance(sr) == true) sr = sr.left; else sr = sr.right; setNode(it, sr); } }   static boolean treeBalance(Node b){ if((countNodes(b.left) == countNodes(b.right)) || (countNodes(b.left) < countNodes(b.right) )) return true; else return false;}```

--- Update ---

Quote:

Originally Posted by Norm
What variable is null? Why doesn't the code test for the null value before it gets the exception?

One problem I see is too much use of static variables and methods.

It throws the null exception when it tries to access any of the sub-nodes from the root. The nodes are apparently empty, and the root or parent node each has two pointers (left and right). If you call.. say root.left, but a new node hasn't been created at root.left it'll throw a null exception b/c it's not pointing to an existing node I suppose.
• April 18th, 2013, 12:19 PM
Norm
Re: Help with my Binary tree. (Node links are incorrect) Please!
A useful technique for working with linked Nodes is to add a toString() method to the node that returns the data about the node: item, left and right. Then when a Node is printed, the toString() methods are called and the structure of the list/tree is completely displayed.

Another technique I use for debugging code that uses the Scanner class for input is to preload the Scanner with its constructor so that the program automatically answers all questions. Here is a sample:
Code :

``` Scanner input = new Scanner("aaa\nxxx\nccc\nddd\nbb\n\n"); //System.in); ...   Scanner input = new Scanner("1 1 1 3 4"); //System.in); //<<<<moved here   /*static*/ int menuStart(){ // Scanner input = new Scanner(System.in);```

For debugging the code I suggest that you add lots of calls to the println() method to display the execution flow and the contents of all the variables as they are used and changed.

BTW A lot of the code is poorly formatted with improper, inconsistent indentations and hidden }s making it very hard to read and understand.
• April 18th, 2013, 12:30 PM
Jacksla3
Re: Help with my Binary tree. (Node links are incorrect) Please!
Thank you for the debugging advice Norm! I realize the indentation etc. is horrid, that's just me rushing to find a solution & modifying the code. Here's an output of me running the program. Now it isn't appearing to assign anything to root.

Welcome to the Binary Search Tree program.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Jack
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
3
The tree contains 1 unique strings.
Contents of tree:
null
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
2
Please enter the string to search for:
Ash
null
String does not exist in the Binary Tree.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
2
Please enter the string to search for:
Jack
null
String does not exist in the Binary Tree.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
• April 18th, 2013, 01:38 PM
Jacksla3
Re: Help with my Binary tree. (Node links are incorrect) Please!
Here is an output of my program. If this helps. I had a few calls to println already in the problem function, this is what happens.

Welcome to the Binary Search Tree program.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Jack
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
1
Enter new string: Ash
true
Node@c25ae3
Please enter a new command:
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
3
The tree contains 1 unique strings.
Contents of tree:
null
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
2
Please enter the string to search for:
Ash
null
String does not exist in the Binary Tree.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.
2
Please enter the string to search for:
Jack
null
String does not exist in the Binary Tree.
Enter one of the following numbers to use the tree:
1, Add string. 2, Search Tree. 3, Display Tree. 4, Exit program.