Binary Tree Search[HELP]

hello everyone!
I'm have created a binary tree program where the tree is balanced(but not sorted). The Tree hold unique strings in each nodes. if the user enters a non unique string, the node frequency (a field of the TreeNode class) should be increased by one, but no new node is created.Also, there is an option for searching for a string and getting the frequency if the string is found. In order to do this, I need to use recursion to create a search function in the Tree class (the search should use preorder (compare items in the left subtree, then right))
My CODE below:

Code :

---

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.
   	}
	}
}

---

Code :

---

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;
	}
 
}

---

Code :

---

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 = stTree.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 = stTree.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:");
						stTree.preorderPrint(stTree.getRoot());
						System.out.println();
 
 
					break;
			}
 
		}
	}
}

---

I don't have any errors compiling the code, but there is a logic error in the search method in Tree class. when inserting the values A through H, you should get this tree:

HTML Code:

---

                    A
            /                \
          B                    C
      /      \            /      \
    D              F          E        G
    /
  H

---

I noticed when searching for Items in the left subtree (A,B,D,H) the search function works, but for(F,C,E,G) the search doesn't work. Could Anyone please tell me how to fix this logic error?

Quote:

---

I noticed when searching for Items in the left subtree (A,B,D,H) the search function works, but for(F,C,E,G) the search doesn't work. Could Anyone please tell me how to fix this logic error?

---

Think hard about what the search method posted actually does. It will search (and return the result of) the left branch if that child is not null...in affect, never searching the right child of a node if the left is not null. Think about your algorithm, write it out on paper, then translate that to code. One way would be to search the left child, if the value is found return the result, otherwise search the right.

Sorry, but this didn't really help. I understand where is my error, I just have no idea how to fix it. I tried making it look like the preorderPrint class, but it doesn't work because I have to return the found TreeNode which makes things complicated.
I tired this, but with "missing return statement" error.

Code :

---

public static TreeNode search(TreeNode root, String st)
	{
		if(root ==null)
			return null;
		else if(st.equals(root.getString()))
			{	
				return root;
			}
		while(root.getLeft() != null)
		{
				return search(root.getLeft(), st);
		}
		while(root.getRight() != null)
		{
				return search(root.getRight(), st);
		}
	}

---

This also gave the same error!

Code :

---

public static TreeNode search(TreeNode root, String st) 
	{
   	if ( root != null )
		{  
	      if(st.equals(root.getString()))
			{
				return root;
			}
			search( root.getLeft(), st);
	      search( root.getRight(), st );
   	}
		else
		return null;
	}

---

Can you please suggest a fix? I spent hours on this with no luck :confused:

Quote:

---

Can you please suggest a fix?

---

...

Quote:

---

Think about your algorithm, write it out on paper, then translate that to code. One way would be to search the left child, if the value is found return the result, otherwise search the right.

---

I understand what you guys are saying, its just that putting it in code is is a bit tough for me :confused:
I have to search in preorder using recursion to compare the strings, and if a match is found, I have to return its corresponding TreeNode.

This is my last try, and it still doesn't work *surprise* . I think the problem is the "return null" in the else statement in "search", but removing it creates this error --> "missing return statement"

Code :

---

public boolean compare(TreeNode root, String st)
	{	
		if(st.equals(root.getString()))
		{
			return true; 
		}
		else 
			return false;
	}
	public TreeNode search(TreeNode root, String st)
	{
		if(root==null)
		{
			return null;
		}
		else if(compare(root, st) == true)
		{
			return root;
		}
		else
		{
			search(root.getLeft(), st);
			search(root.getRight(), st);
			return null;
		}
	}

---

Please help me out guys, this is driving me crazy :(