I am supposed to create a binary tree using strings typed in by the user, to build a balanced tree using recursion. When I type in letters: A, B, C, D, E, F
and the output is set up for preorder output, what I am getting is:A B D F C E
according to my understanding of preorder traversal the output should be: A B D E C F

where did I go wrong here?
first is my main class, then my tree class, then treenode class

import java.util.*;


public class TreeDriver {

    public static void main(String[] args) {

        Tree myTree = new Tree(); 

        Scanner keyboard = new Scanner(System.in);
        int input;

        while(true){
            System.out.println("\nSelect your option!");
            System.out.println("\t1 - Enter a new String");
            System.out.println("\t2 - Search for a String");
            System.out.println("\t3 - Display Tree");
            System.out.println("\t4 - Exit");

            input = keyboard.nextInt();
            Scanner scanner = new Scanner(System.in);


            if(input == 1){
            System.out.println("Enter a new string: ");
            String word = scanner.next().toUpperCase();
            myTree.insert(word);
            System.out.println("Inserted " + "'" + word + "'" + " into tree");

            }else if(input == 2){
            System.out.println("Enter a string to search: ");  
            }else if(input == 3){
            System.out.println("Display Tree: ");
            myTree.preOrder();

            }else if(input == 4){
                System.exit(0);//exit program
            }
            System.out.println("\nEnter another option");
            }           
       }
    }

Tree Class

public class Tree {

    public TreeNode root;    

    public Tree(){

        root = null;

    }

        public TreeNode returnRoot(){
            return root;
        }

    public boolean isEmpty(){

        return root == null;

    }

    public void insert(String value){

        if(isEmpty()){

            root = new TreeNode(value);

        }else{

            root.add(value);

        }
    }
        public TreeNode getRoot(){
            return root;
        }

         public void preOrder() {
        preOrder(root);
    }

          // using the function ...
       public void preOrder(TreeNode root) {
         if (root != null) {            

       System.out.println(root.getWord());   // root
       preOrder(root.getLeft());        // left
       preOrder(root.getRight());       // right
}

       }
}

TreeNode class

public class TreeNode {

        private String word;    // The data in this node.
    private TreeNode left;   // Pointer to the left subtree.
    private TreeNode right;  // Pointer to the right subtree.

    public TreeNode(String s){
        word = s;
        left = null;
        right = null;
    }


    public void add(String value) {

        if (left == null) {     
            left = new TreeNode(value);     
        } else if( right == null){      
            right = new TreeNode(value);            
        } else {        
            if(countNodes(left) <= countNodes(right)){               
                left.add(value);                
            } else {        
                right.add(value);

            }   
        }
    }

    //Count the nodes in the binary tree to which root points, and
    public static int countNodes( TreeNode root ) {
        if ( root == null ){

            // The tree is empty.  It contains no nodes.
            return 0;  

                }else {

            // Start by counting the root.
            int count = 1;   


            // Add the number of nodes in the left subtree.
            count += countNodes(root.left);

            // Add the number of nodes in the right subtree.
            count += countNodes(root.right); 

            return count;  // Return the total.
        }
    }

        public TreeNode getLeft(){
        return left;
    }

    public TreeNode getRight(){
        return right;
    }

    public String getWord(){
        return word;
    }



}

The problem is with your tree construction , binary trees have the rule that all nodes are less than every node in their right substree and greater than or equal to nodes in their left subtree.There is no where in your code where you extract each individual character of the string and compare it to another.

That's a pretty strange binary tree. Normally, insertion criteria is based on the "value" attribute of each node which helps you determine where to insert a node into a tree and at the same time, how to "search" for a node inside the given tree. With the number of nodes used as an insertion criteria, how do you plan on finding a given node in the tree?

Anyways back to the question; with the current code, the output of A B D F C E is expected. Trace the tree on a piece of paper for the input you suggested. What kind of tree do you get? Any reason why you think A B D E C F should be the output?

EDIT: Gah, replying to a stale thread...

Edited 3 Years Ago by ~s.o.s~

I thought that when I inserted the characters into the tree that the would be inserted as such:

              A
            B   C                
          D  E  F

but apparently they are being added as:

              A
            B   C
          D  F   E

Now, just to be clear, this is not a binary search tree, just a binary tree. The letters are being added into the tree as the 2nd demonstration.

Now I have a problem with finding values on the right subtree.
I have added some code, that will search for a letter that was entered by the user, if it is found it will increase the frequency of the letter.

It will output for the root, and the left subtree, but does not return anything for the right subtree.
I will paste below.

Another question.... Am I supposed to compare string values for the input for a balanced binary tree?
If so, can you help me get started?
pasting whole program below:

Main:

import java.util.Scanner;

public class TreeDriver
{
    public static void main(String [] args)
    {
        String st;
        int option = 0;
        Scanner keyboard = new Scanner(System.in);
        Scanner stKeyboard = new Scanner(System.in);
        Tree stTree = new Tree();
        TreeNode compareNode;

        while(option != -1)
        {
            System.out.println("1. Enter a new String.\t"+
                                    "2. Search for a String.\t"+
                                    "3.Display Tree.\t"+
                                    "-1. To Exit.");
            option = keyboard.nextInt();


            switch(option)
            {
            case 1:
                System.out.println("Enter the string you would like to add to the tree: ");
                st = stKeyboard.nextLine();

                compareNode = Tree.search(stTree.getRoot(), st);

                if(compareNode != null)
                {
                    compareNode.upFreq();
                    System.out.println("\tRepeated String. Frequency +1.");
                }
                else
                {
                    stTree.insert(st);
                    System.out.println("\tString inserted.");
                }

                break;

            case 2: 
                System.out.println("Enter the string you would like to search for: ");
                String searchST = stKeyboard.nextLine();

                compareNode = Tree.search(stTree.getRoot(), searchST);
                if(compareNode != null)
                {
                    System.out.println("FOUND - "+compareNode.getFreq());
                }
                else
                {
                    System.out.println("NOT FOUND.");
                }
                break;

            case 3: 

                    System.out.println("Preordered Strings:");
                    Tree.preorderPrint(stTree.getRoot());
                    System.out.println();


                break;
        }

    }
}
            }

Tree Class

public class Tree
{
    private TreeNode root;

    public Tree()
    {
        root = null;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public void insert(String st)
    {
        if (isEmpty())
        {
            root = new TreeNode(st);
        }
        else
        {
            root.add(st);
        }
    }

    public TreeNode getRoot()
    {
        return root;
    }

    public static TreeNode search(TreeNode root, String st)
    {
        if(root == null) 
        {
            return null;
        }
        else if(st.equals(root.getString()))
        {
            return root;
        }
        else 
        {   if (root.getLeft() != null)
                return search(root.getLeft(), st);
            else
                return search(root.getRight(), st); 
        }
    }
    public TreeNode found(TreeNode root)
    {
        return root;
    }
    public static void preorderPrint(TreeNode root) 
    {
    if ( root != null )
        {  
          System.out.print( root.getString() + " " );  // Print the root item.
          preorderPrint( root.getLeft() );   // Print items in left subtree.
          preorderPrint( root.getRight() );  // Print items in right subtree.
    }
    }
}

TreeNode Class

public class TreeNode
{
    private int freq;   //frequency of the String in the Node
    private String stValue;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(String st)
    {
        stValue = st;
        left = null;
        right = null;
        freq = 1;
    }

    public void add(String st)
    {   
        if (left == null)
        {
            left = new TreeNode(st);
        }
        else if (right == null)
        {
            right = new TreeNode(st);
        }
        else
        {
            if(countNodes(left) <= countNodes(right))
            {
                left.add(st);
            }
            else
            {
                right.add(st);
            }
        }
    }

    //Count the nodes in the binary tree to which root points, and
    public static int countNodes( TreeNode root ) {
        if ( root == null )

            // The tree is empty.  It contains no nodes.
            return 0;  

        else {

            // Start by counting the root.
            int count = 1;   


            // Add the number of nodes in the left subtree.
            count += countNodes(root.getLeft());
            // Add the number of nodes in the right subtree.
                        count += countNodes(root.getRight()); 

                        return count;  // Return the total.
                    }
                }



                public TreeNode getLeft(){
                    return left;
                }

                public TreeNode getRight(){
                    return right;
                }

                public String getString()
                {
                    return stValue;
                }

                public void upFreq()
                {
                    freq = freq + 1;
                }
                public int getFreq()
                {
                    return freq;
                }

            }

Now I have a problem with finding values on the right subtree.
I have added some code, that will search for a letter that was entered by the user, if it is found it will increase the frequency of the letter.

It will output for the root, and the left subtree, but does not return anything for the right subtree.

This is because you never search the right sub-tree if the value isn't found on the left sub-tree. You need to change your condition so that both left and right sub-trees are searched in your search method of the Tree class. Also, I hope you are aware that you lose the "find node in logarithmic time" feature offered by the search trees if you don't create your tree based on value but the number of nodes it has.

Another question.... Am I supposed to compare string values for the input for a balanced binary tree?

I'm not sure I understand this question: you are already searching for the nodes based on their string values?

Edited 3 Years Ago by ~s.o.s~

I am sure that a search tree would be more efficient, but this is an assignment, and specifically needs to be just a binary tree.

That is my question, how or what to add for the conditional statement to search the right subtree?

Replace the else in the search method with another if statement which checks if the right sub-tree is not null and checks it.

I changed the code to this:

public static TreeNode search(TreeNode root, String st)
    {
        if(root == null) 
        {
            return null;
        }

        if(st.equals(root.getString()))
        {
            return root;
        }

        if (root.getLeft() != null){
            return root.left;   
        }
        else{
            return search(root.getRight(), st); 
        }
    }

Trace your algorithm on a piece of paper before making changes. The code right now directly returns the left subtree node if the left sub-tree is non-null, something which is not desirable. Your top two conditions (the first two if's in the search function) are correct. The third if..else needs to be replaced by two if's. Something like:

  • If left sub-tree is not null, search left sub-tree (you had this correct in the previous attempt)
  • If right sub-tree is not null, search right sub-tree
  • Return null if all else fails

Edited 3 Years Ago by ~s.o.s~

I am getting this error:

Exception in thread "main" java.lang.NullPointerException
    at Tree.isFound(Tree.java:50)
    at TreeDriver.main(TreeDriver.java:34)
Java Result: 1

I will post code below, I am attempting to increase the frequency by 1 if the word already exists when I enter a new word, or search for the word, which will out put found if it exists plus the frequency.

Main class

import java.util.*;


public class TreeDriver {

    public static void main(String[] args) {

        Tree myTree = new Tree();        

        Scanner keyboard = new Scanner(System.in);
        int input;



        while(true){
            System.out.println("\nSelect your option!");
            System.out.println("\t1 - Enter a new String");
            System.out.println("\t2 - Search for a String");
            System.out.println("\t3 - Display Tree");
            System.out.println("\t4 - Exit");

            input = keyboard.nextInt();
            Scanner scanner = new Scanner(System.in);            

            if(input == 1){
            System.out.println("Enter a new string: ");            
            String word = scanner.next();
           if(myTree.isFound(word) == true){
               System.out.println(word + " already exists increase frequency by +1");
           }else{
             //if string input by user is found increase frequency by one
             //and output System.print.ln(word + " found in tree, increase freq. by +1);
           //if word does not already exist....
            // }else{ 
            myTree.insert(word);
            System.out.println("Inserted " + "'" + word + "'" + " into tree");       
           }
            }else if(input == 2){
            System.out.println("Enter a string to search: ");          
           String word = scanner.next();
            //after user inputs word for search
            //return search(); will display whether word was found or not
            //and will include frequency of that word.
           if(myTree.isFound(word) == true){
            //myTree.search(wordS);                
                System.out.println("FOUND - " + myTree.search(word.toString()).getFreq());
           }else if(myTree.isFound(word) == false){
                System.out.println("NOT FOUND.");
           }  

            }else if(input == 3){
            System.out.println("Display Tree: ");
            myTree.preOrderPrint();

            }else if(input == 4){
                System.exit(0);//exit program
            }
            System.out.println("\nEnter another option");
            }           
       }
    }

Tree Class

public class Tree {

    TreeNode root;    

    public Tree(){

        root = null;

    }        

    public boolean isEmpty(){

        return root == null;

    }

    public void insert(String word){

        if(isEmpty()){      
            root = new TreeNode(word);                        
        }else{          
            root.add(word);              

        }
    }

        public TreeNode getRoot(){
            return root;
        }

        public TreeNode search(String word)
    {               
                  while(root.word.equals(word)){
                    if(root.left != null){
                        root = root.left;
                    }
                    if(root.right != null){
                        root = root.right;
                    }else{
                        return null;
                    }
                  }
                  return root;
        } 

        public boolean isFound(String word){
           boolean found = true;

             while(root.word.equals(word)){
                 if(root.left != null){
                        root = root.left;
                } 
                if(root.right != null){
                        root = root.right;
                    }else{
                        root = null;
                    }
                  }
                  return found;
        }

         public void preOrderPrint() {
        preOrderPrint(root);
    }

          // using the function ...
       public static void preOrderPrint(TreeNode root) {
         if (root != null) {            

       System.out.println(root.getString());   // root
       preOrderPrint(root.getLeft());        // left
       preOrderPrint(root.getRight());       // right
}

       }

    }

Treenode Class

class TreeNode{


        public String word;    // The data in this node.        
    TreeNode left;   // Pointer to the left subtree.
    TreeNode right;  // Pointer to the right subtree.
        public int freq = 1;

    public TreeNode(String w){
        word = w;
        left = null;
        right = null;

    }


    public void add(String word) {

        if (left == null) {     
            left = new TreeNode(word);      
        } else if( right == null){      
            right = new TreeNode(word);         
        } else {        
            if(countNodes(left) <= countNodes(right)){               
                left.add(word);             
            } else {        
                right.add(word);

            }   
        }
    }

    //Count the nodes in the binary tree to which root points, and
    public static int countNodes( TreeNode root ) {
        if ( root == null ){

            // The tree is empty.  It contains no nodes.
            return 0;  

                }else {

            // Start by counting the root.
            int count = 1;   


            // Add the number of nodes in the left subtree.
            count += countNodes(root.left);

            // Add the number of nodes in the right subtree.
            count += countNodes(root.right); 

            return count;  // Return the total.
        }
    }





        public TreeNode getLeft(){
        return left;
    }

    public TreeNode getRight(){
        return right;
    }

    public Object getString(){
        return word;
    } 
         public void upFreq(){
            freq++;
        }

        public int getFreq(){
            return freq++;
        }




}

Which IDE are you using for development? Use a debugger a check why that line has a null root. The assignment on line 56 seems to be causing the problem because you don't do a null check on the root before using it on line 49.

This question has already been answered. Start a new discussion instead.