problem with Binary tree.. plse help

[ezkonekgal]

I have a problem:
1.) How do you insert a sequence of integers into a binary tree? does anybody have an algorithm for it?

like input : 1, 5, 3, 4 ,2

binary tree:
1
5 3
4 2

[javaAddict]

First you need to define what kind of structure to use in order to represent your tree. An array for example. Then you write code that inserts and reads the data, at and from the right place

[ezkonekgal]

the structure that i want to use is node or link..
do i use recursion on this?

[verruckt24]

Yes recursion is very efficient in case of trees. I suppose from your question in the first post that you want to know how to load the tree.
Well this depends on what purpose you want to use the tree for. If you are using the tree for sorting, you populate the tress in this way.
First element becomes the root, then for every element after that, we (recursively) decide it's position depending upon whether the element at the current node is greater than or less than the element to be inserted. If the element to be inserted is greater than the element at the current node we move to right of the current node else to left node of the current node. For elements found to be equal we can decide either way, in this case we decide to move towards the left node of the current node.

Applying the above given algorithm to the numbers you have given we proceed to build the tree this way:
Sequence of numbers : 1,5,3,4,2
1
5
3
2 4
Here number 1 is at the root, number 5 to it's right node, number 3 to the left node of 5, number 2 on the left node of 3, number 4 on the right node of number 3.
Now a normal Inorder traversal of the tree would yield you a sorted list.

In inorder traversal we first visit the left node,then the root and then the right node. We go on printing the numbers as we visit the nodes.
To traverse the tree we built above, we would first print the root element since there's no left node side of it, so we print 1, then move on to the nodewith number 5, but we don't print it since there is a left hand side of it, we move there, but there again it has a left node so we move there which does not have a left node so we print it out, thus printing 2, then we print 2's parent node which is 3 then it's right node which is 4 and then coming back to 3's parent node we print out 5, now the node with 5 does not have any right side node so we can stop printing, and as a result we have the sorted list 1,2,3,4,5 with us !!!

[ezkonekgal]

No, the tree isn't for sorting. I want to put the numbers example 1,2,3,4,5 in the binary tree. then it should be like this:

1, is in the root.
2, is in the left of the root
3, is in the right of the root
4 and 5 are now sons/children of 2 and are in the left and right of r respectively.

Now if i want to input more, like 6 and 7. then this would be inserted as being children of 3.

I have this method:

public void treeInsert(String newItem) {

		       if ( root == null ) {
		              // The tree is empty.  Set root to point to a new node
		              // containing the new item.
		          root = new BinaryTreeNode( newItem );
		          return;
		       }
		       BinaryTreeNode runner; // Runs down the tree to find a place for newItem.
		       runner = root;   // Start at the root.
		       while (true){
		    	   if ( runner.left == null ) {
		    		   runner.left = new BinaryTreeNode( newItem );
		    		   return;  // New item has been added to the tree.
		    	   }else if ( runner.right == null ) {
		    		   runner.right = new BinaryTreeNode( newItem );
		    		   return;  // New item has been added to the tree.
		    	   }else if (runner.left != null && runner.right != null){
		    		   if(runner.left.left == null){
		    			   runner.left.left = new BinaryTreeNode(newItem);
		    			   return;
		    		   }else if (runner.left.right == null){
		    			   runner.left.right = new BinaryTreeNode(newItem);
		    			   return;
		    		   }
		    		   runner = runner.right;
		    		   if(runner.left == null){
		    			   runner.right= new BinaryTreeNode(newItem);
		    			   return;
		    		   }else if (runner.right == null){
		    			   runner.right = new BinaryTreeNode(newItem);
		    			   return;
		    		   }
		    	   } runner = runner.left;
		       
		       }

i can't seem ti get this right...

[verruckt24]

Use recursion to insert nodes. Recursion is basically a function calling itself. A simple example of recursion is as follows:

int factorial(int n) {
   if (n == 0)
      return 1;
   else
      return (n * factorial(n-1));
}

[ezkonekgal]

Recursions the part where i break up.. the above method i posted should be recursive but it seems that isn't. I'm having a hard time figuring out because there are a lot of considerations in inserting into a node. Like wether if it should be in the left son or right son. Its like when you delete from a complete binary tree, it is in reverse level order, right to left, bottom-up. Now if i want to insert stuffs in it, it should be from left to right, top to bottom...

[verruckt24]

Read post #6 by me again, it is a typical example of recursion to calculate the factorial upto a number n. The method you have shown is not recursion, since recursion is a call to the same function within that function itself. So if you see the recursive method shown in post #6, the factorial method gives a recursive call to itself with one less than the number. Meaning a call to factorial(n) would result in a recursive call to factorial(n-1) which in turn would result in a call to factorial((n-1)-1) and so on till the termination condition of the recursion occurs which is when n finally becomes 0.

In your case, whenever you give a call to treeInsert(node) you need to check if node.left is null, if yes, create a new node, insert the data into it and assign this node to node.left, if node.left is not empty, do the same for node.right, if that too is found to be not empty, give a call, and here is where recursion comes in, to treeInsert(node.left) and the story continues in node.left.

[ezkonekgal]

pardon me, you said treeInsert(node). but mine is treeInsert(newItem). Am i wrong in doing this? because further you said treeInsert(node.left) which i can't do.. are your saying that it should be treeInsert(node)?

[verruckt24]

It should be treeInsert(node, data) rather, where node is whose left and right are to be searched for a place to insert the new data. Once you find such node you create a new node with the data inside it and put its reference in the node's left or right part. Read my previous post again with the changes mentioned here.