Java recursive binary tree

[TigerGirl]

Hi.
I have a recursive public static method search that takes a Tree node (any arbitrary binary tree, not necessarily a search tree) and returns whether or not that tree satisfies the order property for a binary search tree. So, my method is

public static boolean search(TN t)
  {
    if (t == null)
      return true;
    else
      if (t.value == t.next.value)
         return search(?);  // I don't know what I should put there
      else if (toFind < t.value)
         return search(t.left, t.next.value);
      else
         return search(t.right,t.next.value);
  }

[bentlogic]

So do you want to stop the recursion at this point (as node found)? If yes, then what about supplying the inductive node base case? Will that 'unwind' the recursion upon treenode found? Not sure if I'm wasting your time really...

[TigerGirl]

What do you mean by the inductive node base case? I thought I already have that.

[bentlogic]

This is day 2 awake so not real cognitive... I see your base case when node is null.

In terms of knowing what param to put on line 7 ( I'm so tired a 'shiny pony' will do just fine ) what about null. Can we pass back null to stop the recursion without throwing a nullpointerexception in java?

I dunno, sorry! :)

[bentlogic]

Let's have another stab and I promise it's the last one :)

that was just silly above; I don't understand the algorithm but what about ending the recursion when either condition occurs, i.e.

if( (t == null) || (t.value == t.next.value) ) 
return true;

[TigerGirl]

yeah! that sounds about right, I have to check it, but what about the else do you think that the way that I used to call the method is correct??

[jmaat7]

Sorry If i'm overlooking something simple, but doesn't your method only take one parameter? (TN t)

the call to the method in the else statements try to pass 2 parameters
(t.left, t.next.value)

[TigerGirl]

You're right! So would I instead call t.left then? is the code even right?

[jmaat7]

Actually, I think you're missing some code. the base case looked fine the way it was, because you'll be moving down the branches until you hit a null anyway. there's no reason to compare weather they're ==.

yeah for this you would just pass t.left as the parameter for the method i mentioned above. But what are you setting toFind to? This method looks like it will run down only 1 side of the tree.

ex:
for a balanced tree, traversing from the top
5,3,7,1,9

if toFind is initially set to 7 it and t is the first node(5) it will compare 7 to 5 and recursively move to the left. but that will return a null showing that the tree is unbalanced.

I think the code is more complex than this, i had a similar problem in my data structures course. I think the way I did it was by running down each branch and setting a counter for the levels, then i would compare the counters with the other side of the branch to make sure they were balanced. I got the grade, but the teacher said it was overkill.

I think I remember using the recursive method 2x (the first one with the left, second with the right). Basically, I traversed the tree starting from the top and counted that the levels were the same at the end.

I'll try to look up my old assignment, but in the meantime good luck.

[TigerGirl]

Thanks, I really need an example, because right now, I have no clue what to do for the else, but I have one more question. So, instead of returning an else, should I just make statements, because the method keeps returning false no matter what.