Binary Tree Help

H

Hexus0

Gawd
Joined
Feb 28, 2005
Messages
590
Hey everyone, I'm working on an assignment for my data structures class and I'm having some trouble trying to understand an algorithm for a method. The method searches a binary tree (composed of strings) to check if any of the nodes are the reverse of the other (ie "cat" and "tac"). I've written a search method and tried to alter it for this, but I'm not having any luck, so I decided to start from scratch and just try to figure out the algorithm. I'm just having a problem understand how to search and compare each node. Any help or suggestions are appreciative.

Thanks!
 
Are you trying to figure out if any node contains a string that's the reverse of any other node?

Is the binary tree ordered? That is, is it a binary search tree?
 
Its a binary search tree composed of Strings. They're ordered in alphabetical order, sort of.
This is an example of one:
Code: 
                    Cat
              Bar          Dog
                 Car          Fat
                           Eat    Tar
                                      Rat

So after running the "reverseAlso" method it will return a pointer to either tar or rat, because they are a palindrome.

Thanks for the quick reply btw..
 
Okay. So, where is it that you're hung up? I'd do it, by:

Code: 
Try to find the string
	got it? return it
Reverse the string
Try to find the reversed string
	got it? return it
return NULL
 
I'm having a hard time understanding how to traverse through the list, this is what I have (but its just going on forever):

Code: 
	public static StringNode reverseAlso(StringNode x, StringNode y) {
		StringNode rtn;
		if(x == null) {
			rtn = null;
		} else {
			if(reverse(x.getString(), y.getString()) > 0) {
				rtn = x;
			} else if(x.getString().compareTo(y.getString()) > 0) {
				rtn =	reverseAlso(x, y.getRight());
			} else {
				rtn = reverseAlso(x, y.getLeft());
			} 
		}
		return rtn;
	}

The professor didn't give too much information, the way its used in the program is that it passes in the tree to a method and then another method is suppose to make a recursive call to return a node. I should also note I wrote a reverse method, to return 1 if its a palindrome or a 0 if its not.
 
What if you have a node with the string "racecar"?

You're still lacking abit in your problem description. Are you providing a string, and then searching for it's palindrome in the tree? Or are you searching the tree for the set of all nodes who's palindrome appears?

I'm hoping it's something similar to the second option I mentioned, otherwise I think you have some more basic principles of the structure you need to learn.

What methods have you written so far for tree operations? I assume a search method that will return a node if it contains a certain string you're searching for. (Or at least something similar). How could this method be used to help you? Have you succeeded in writing methods for traversing your tree?

I'm afraid to go into too much detail, since you didn't post code, and I don't want to just give it away for you. If it was simply a matter of a slight mistake in your algorithm, I would be more happy to point out details, but I don't want to give the answer away to you.

EDIT: I was posting this during your last reply, where I see code now. Little confused as to exactly what you're doing. Read through mike's last post, and my post. I think you're making it a bit too difficult.
 
I understand and I also understand I haven't gone into much detail, so I'll explain it.

Firstly, I've written an insert, a search, a height, a copy, and a leaf count method. I'm now working on the "reverseAlso" method. Basically, the method checks for any palindrome in the tree, it doesn't provide a string to check for, it just checks every node in the tree to see if there is a palindrome and returns the pointer to either node (the word or the reversed).

My problem is understanding how to check and compare every node with one another, I have yet to do anything like that. I'm re-reading your edit (sorry about the confusing back and forth replies), are you suggesting using the search method to find a palindrome?
 
You know how to traverse the tree because you've written a search method, couldn't you traverse through the tree, and for each node you visit, search the tree for its palindrome?

I have a feeling there may be a follow up question regarding the Computational Complexity of the algorithm?
 
As far as complexity, he says that the faster the algorithm the most points you'll get. I'm really just worried about taking care of the problem first lol.

Should I still follow the order of what mikeblas had said? Because I'm a little confused, how can I search for a string and then go to the next one if I don't find one?

Edit: More specifically what I don't understand, so lets say it searches the string of the root and it doesn't find it, then it goes to the left, which has 2 nodes a left and a right, how to make it go to both of them?
 
In a binary search, it's never necessary to examine both of the children of some node.
 
Hexus0 said:
Edit: More specifically what I don't understand, so lets say it searches the string of the root and it doesn't find it, then it goes to the left, which has 2 nodes a left and a right, how to make it go to both of them?
Click to expand...
Like the previous poster said, from the way a binary tree is constructed, you always know which way to go if you're searching for a single value. And the code you posted does exactly that. There's just one small problem...

The most fundamental requirement for a recursive function (and almost invariably the cause of an infinite loop in such a function) is that the recursive calls have to take you closer to the base case.

EDIT: Never mind... Just had a more thorough read of the thread. If you've got search() defined already, you don't really need that reverseAlso().

Seems where you're stuck is with traversal. This should have been the very first algorithm covered for trees, but here it is anyway (for an in-order traversal):
Code: 
InOrder(n)
{
    if baseCase(n)
        bail
    else
        InOrder(n.left)
        doSomethingWith(n)
        InOrder(n.right)
}

EDIT: One more thing, regarding your reverse() method... Any method which returns either a 0 or a 1 should be returning a boolean ;)
 
I've been messing with some ideas on how to get it to work, but its only returning null. I've changed around my reverse() method to just create a reverse of the string being passed in and I've been trying to use my search method for that.
This is what I have:
Code: 
  public StringNode reverseAlso() {
      return reverseAlso(root);
   }
  
   private static StringNode reverseAlso(StringNode n) {
      StringNode rtn;
      if(n == null) {
         rtn = null;
      } else {
         if(search(reverse(n.getString()), n) != null) {
	   rtn = rtn = search(reverse(n.getString()), n);
	 } else if(search(reverse(n.getString()), n.getRight()) != null) {
	   rtn = search(reverse(n.getString()), n.getRight());
	 } else {
	   rtn = search(reverse(n.getString()), n.getLeft());
	}
      }
      return rtn;
   }
        
   public static String reverse(String x) {
      String s = "";
      for(int i = 0; i < x.length(); i++) {
         s = s + x.charAt(x.length()-1-i);
      }
      return s;
   }

Edit: Now I'm really far off, realized I'm not even traversing through the list...

If anyone is wondering this is my search method:
Code: 
   public StringNode search(String s) {
      return search(s, root);
   }
  
   private static StringNode search(String sv, StringNode n) {
      StringNode rtn;
      if(n == null) {
         rtn = null;
      } else {
         if(sv.equals(n.getString())) {
            rtn = n;
         } else if(sv.compareTo(n.getString()) > 0) {
            rtn = search(sv, n.getRight());
         } else {
            rtn = search(sv, n.getLeft());
         }
      }
      return rtn;
  }
 
Are you looking for palindromes or word reversals? They are not the same thing and steps taken to perform the search of each would probably be different as well since a search for a palindrome of a word is the same as searching for the word itself.
 
I realized that, just word reversals, not palindromes, sorry about that.
 
Your search routine looks fine to me. Have you tried implementing the pseudo code I suggested earlier, using your search routine?

ReverseAlso() doesn't make much sense, because you're making two different decisions at the same time, and end up in the wrong spot in the tree.
 
Suggestion: Start from scratch on that reverseAlso() definition. Most of the stuff you copied across from search() isn't needed for a traversal (Search makes decisions, traversal doesn't, except for the base case test).

What exactly are you supposed to return? If you need to find all word reversals, you'll have to think about how you're going to return several nodes at once.
 
You must log in or register to reply here.
Back
Top