having trouble with recursion

[Adam Chalkley]

Hi guys I am having a hard time understanding recursion in particular how it returns data,this binary tree recursive algorithm is give me trouble,so let me give you some background as to what I understand and what I don't ok as to recursion lets use the go to example of factorial I understand how that happens when the base case is met lets say x == 1 for factorial 1 is returned to the calling method(return x *  factorial(x -1)) x is then multiplied by the returned value(result) of factorial(x-1),this process continues with the results being returned and multiplied until all the methods are returned from the stack in the end the factorial number will be returned I understand how that works but this algorithm in particular is give me trouble,

I understand how the code works but the recursive part is giving me problems,I know what happens when the code runs we set newNode to refer to the result of the insert method which will return the root  of the tree,the root will always be returned,anyway so we call insert with the null tree and the value 5,a new node is created with the value 5 and it's reference nodes are pointing to null,then this newly created Node is returned and control returns to the main method newNode now points to that newly created object which is the root,now we call insert again with newNode and  8, newNode is not null so it is checked with the conditions 8 is greater than 5 so tree.right(newNode.right) equals insert(null(because tree.right equals null), 8), so the insert function gets called again the value passed in is null so it creates a new Node with the value 8 and returns the newObject then the code returns the root node,next we call insert with newNode and 2 but lets skip that because that will go to the other reference,we then call insert with newNode and 9,NewNode is not null it then checks to see if it is greater than tree.right which it is being that tree.right is 5, so tree.right equals insert(tree.right(which is pointing to the object with value 8), 9); the recursion begins and now 9 is checked to see if it is greater than 8 which it is so tree.right equals insert(tree.right( which is now null), 9), as the call happens again it is checked to see if it == null which it does so a new node is created,I understand all that but this is the part that confuses me with this particular algorithm so the stack in memory for this program now has 3 methods on top of each other the main,then insert with the object value 8,then insert with null,so I don't get what happens next first the newly created object with value 9  is returned then,the object with the value 8 is returned,so if the object with the value 8 is returned wouldn't that mean that tree.right = the object with the value 8,in turn tree is returned and newNode is now altered so that means newNode.right equals the object with the value 8,but clearly that is wrong because if that was the case the tree wouldn't work and it does work when I use the search function so it has been implemented correctly but how wrong am I?

I spent a long studying and trying to figure this out and spent some time trying to explain it,I'm just mind boggled at the moment,I thought I was really hitting some strives with my programming skills but this is an obstacle that I'm finding hard to get over,if anybody would be so kind to help me with this problem I would be more than thankful and a lot of stress will be taken from my shoulders before my college repeat exams next month,

Thanks guys really appreciate it and I apologize for it being so long but it's the only way I could explain it.

public class Tree {
	
	
	public Node insert(Node tree,int value){
		
		if(tree == null){
		
		Node newNode = new Node();
		newNode.data = value;
		newNode.left = null;
		newNode.right = null;
		return newNode;
		
	 }
		if(value < tree.data){
			
			tree.left = insert(tree.left,value);
			
		}else{
			
			tree.right = insert(tree.right,value);
		}
		
		return tree;
	}
	
	public Node search(Node tree,int value){
		
		
		if(tree == null){
			
			return null;
		}else if( value == tree.data){
			
			return tree;
		}else if(value < tree.data){
			
			
			return search(tree.left,value);
			
		}else{
			
			return search(tree.right,value);
			
		}
	}
}



class Node{
	
	int data;
	Node right;
	Node left;
	
}

public class Main {

	public static void main(String[] args) {
		
          Node newNode = null;
          Tree main = new Tree();
          newNode = main.insert(newNode, 5);  // newNode now points/refers to new Node with data value 5
          newNode = main.insert(newNode, 8);
          newNode = main.insert(newNode, 2);
          newNode = main.insert(newNode, 9);
          newNode = main.insert(newNode, 12);
          newNode = main.insert(newNode, 35);
          newNode = main.insert(newNode, 7); // newNode now points to new Node with data value = 7
          
          // So how can the search method work if newNode's right value and left value are NULL won't the recursion call just return
          // null but yet somehow the code works and finds the node with the value 
          
          System.out.println(main.search(newNode, 8).data);
	}

}

[Campbell Ritchie]

Start by trying recursion to find a value in the tree. Let's assume that you have a tree containing values of a type which implements Comparable. Let's call that type Foo such that Foo implements Comparable<Foo>. Let's assume that the node objects are not visible to any code outside the tree object. Let's have a method which simply returns true or false depending on whether the value sought is found. Let's assume that every node has a value and that value is never null, and left and right branches but they might be null. You can use Integer instead of Foo; it fulfils all your requirements.

Now, draw a diagram of a tree like that. It doesn't matter how many nodes it contains, but let's have at least six nodes otherwise it is going to be too simple to search. Now, search the tree with your pencil and explain what you are doing. You might do well to listen to the episode of Cabin Pressure where they talk only in monosyllables first, because the smaller the words you say, the better. Don't try to visualise the code. Try to visualise what your pencil is doing. At each node, say what is happening and how you decide whether you have found the value sought or decided you have reached a dead end. I presume you have been told what branching nodes and leaf nodes are.

[Henry Wong]

Adam Chalkley wrote: I understand all that but this is the part that confuses me with this particular algorithm so the stack in memory for this program now has 3 methods on top of each other the main,then insert with the object value 8,then insert with null,so I don't get what happens next first the newly created object with value 9  is returned then,the object with the value 8 is returned,so if the object with the value 8 is returned wouldn't that mean that tree.right = the object with the value 8,in turn tree is returned and newNode is now altered so that means newNode.right equals the object with the value 8,but clearly that is wrong because if that was the case the tree wouldn't work and it does work when I use the search function so it has been implemented correctly but how wrong am I?

I think you may be overthinking it .... the main task of the return is just to backtrack (ie. to unroll the stack).

The only significant change is the node 9, which is assigned to the right reference of node 8, after it is returned. All the other returns are moot. They return the original value, that was passed in, and assigned to the original reference. This means that all of the other assignments do not change anything.

Henry

[Campbell Ritchie]

Notice there were some things I said which seem to differ from your code. The tree might be visible to outside code, but the nodes oughtn't to be. The structure of nodes shou‍ld be visible only to the tree. I think you need to rethink the design of your tree.
* * * * * * * * * * * * * * * * * * * * * * * *
You shou‍ld end up with a method something like this:-

public class Tree<T extends Comparable<? super T>> ...
{
   // ...
   public boolean contains(T t)
   {
      return root != null && root.contains(t);
   }
   // ...
   private class Node
   {
      private T value;
      private Node left;
      private Node right;
      // ...
      private boolean contains(T t)
      {
         int i = value.compareTo(t);
         return i == 0 ||
                i <  0 && left  != null &&  left.contains(t) ||
                i >  0 && right != null && right.contains(t);
      }
      // ...
   }
   // ...
}

Note that the contains method appears in the tree object, but the recursion is done by the node objects. Note that && and || operators ensure that methods are not called on null references, but they must be used in that order. Note that I can never remember whether compareTo returns positive or negative if you have value on the left.

[Adam Chalkley]

Thanks Campbell and Henry I will study the replies,I do agree though that I am overthinking it a bit,

much appreciated

[Adam Chalkley]

Henry Wong wrote:

Adam Chalkley wrote: I understand all that but this is the part that confuses me with this particular algorithm so the stack in memory for this program now has 3 methods on top of each other the main,then insert with the object value 8,then insert with null,so I don't get what happens next first the newly created object with value 9  is returned then,the object with the value 8 is returned,so if the object with the value 8 is returned wouldn't that mean that tree.right = the object with the value 8,in turn tree is returned and newNode is now altered so that means newNode.right equals the object with the value 8,but clearly that is wrong because if that was the case the tree wouldn't work and it does work when I use the search function so it has been implemented correctly but how wrong am I?

I think you may be overthinking it .... the main task of the return is just to backtrack (ie. to unroll the stack).

The only significant change is the node 9, which is assigned to the right reference of node 8, after it is returned. All the other returns are moot. They return the original value, that was passed in, and assigned to the original reference. This means that all of the other assignments do not change anything.

Henry

Hi Henry that makes a little more sense now so when the stack unrolls and newNode(node with value 9) is returned the calling method then assigns the node with value 9 to tree.rights(trees right reference)? I understand that now but now return is called again and it returns tree,that stack is now taken off the stack frame,but now the next frame this is the one that is confusing me tree is returned from the previous stack frame so wouldn't tree.right = the returned value(which is tree,the original node that was passed in) then tree is returned again and the original node is returned to the main method?

thanks

[Henry Wong]

Adam Chalkley wrote: I understand that now but now return is called again and it returns tree,that stack is now taken off the stack frame,but now the next frame this is the one that is confusing me tree is returned from the previous stack frame so wouldn't tree.right = the returned value(which is tree,the original node that was passed in) then tree is returned again and the original node is returned to the main method?

It is probably a good idea to keep track of what stack frame you are in, and also, the node that is being worked on -- as each stack frame is working on a different node, and hence, have different left and right variables.

Just saying it return "tree" and working on "tree.right" is totally confusing. Each frame has a different tree parameter variable, which points to a different node, and hence, have different tree.left and tree.right variables.

Henry

[Campbell Ritchie]

Are you really calling the nodes tree? That is a sure‑fire recipe for confusion. Be careful about names. You shou‍ld be inside one Tree instance at a time, and you can call that tree. That tree object has a reference to ≤1 node, and that is called root. Yes, the tree either is empty and contains no nodes, or it is full and contains one node. Irrespective of how many values you have added, the tree only has a reference to the root node. Did you realise that? Did you also realise that every time you add a value to the tree, you have to have a node to contain it, and that new node removes one null somewhere and adds two nulls somewhere else, so the number of references pointing to null is one more than the number of nodes/values. That number applies to a binary tree; it would be larger if you have trees with more than two branches per node.
I think you should consider requiring an initial value in the tree constructor; that can be added as the root node's value.
Also consider what you are going to do if you have two values offered which are the same. Most people would ignore the second value and return false from the add() method. That means that, if Comparable is implemented in such a way as to be consistent with equals, you have created an implementation of a sorted set. If you are using ints, there is no such thing as equals(), but i == j, i > j, and i < j will behave as if consistent with equals().
Now, each of your nodes has two other node references usually called left and right. If you look at the recursive suggestion I wrote a couple of days ago, you will see that I only used the names root, left and right. You could consider calling each node currentNode, but that is probably unnecessary because Java® already has a keyword which captures that concept: this.

I notice that my method from earlier doesn't take consideration of the possibility of value being null. You will have to consider whether your tree permits nulls at all, and if so, how you are going to sort it. You might find life simpler if you prohibit nulls for the time being, and throw an Exception in the add method whenever null is offered. If your treee contains ints or other primitives, the problem of nulls cannot arise. It is probably simplest to permit every valid int in its whole range and not to try to restrict the range of values. Always present values out of order. If you present them already sorted, your tree will degenerate into a linked list.

[Adam Chalkley]

Hi guys I didn't want to waste space with a new topic as this kind of relates to the question that was originally asked,anyway the problem I am having is with the search method of this binary tree search algorithm and more specifically with what the return does,ok lets say I enter 9 as the value to try and find like in the code,the search function will check to see if tree == null which it does not ,then it checks to see if the value equals the current nodes data value which is 5 it is greater so it goes to line of code return search(tree.right,value); tree.right is the object with the data value 8 and value is 9,the search method now runs again with these parameters its checked to see if it's equalled to null which it is not then  checked to see if the nodes data value equals the value passed in it does not it is greater so the function gets run again this time with tree.right which equals the node object with data value 9 and with the value 9,it checks to see if it equals null which it does not,then it checks to see if the data value of the current node equals the value passed in it does so it returns that node,I understand all that but this is the part that confuses me(with return),

so 4 stack frames have been put on the stack one for main and three for the search method which include search(node(data val 5),9), search(node(data val 8),9),search(node(data val 9),9) ok so the final stack frame returns the node with the found data value to the caller which is the search function below it,so how does the node get returned when the frames(search methods below it just return the search function itself with parameters example
return search(tree.left,value); how does the node eventually get returned to the main method which where it is used??,I'm not too sure how the return works this way,could someone try to clear this up in simple(ish) terms?

Thanks guys much appreciated