• Post Reply Bookmark Topic Watch Topic
  • New Topic

Insert numbers in a binary search tree  RSS feed

 
rebps arora
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi I am trying to make binary search tree...I am trying to construct the left part of binary search tree with root node set as 70...It is not working ...Can someone please make changes in code so that it works fine...My code is
public class Node {

/**
* @param args
*/

int root;
Node left;
Node right;

public void insertNode(Node node, int num) {
//Node nodeRoot = this;
//root of tree we have set to 70...constructing only left of tree with root=70

if(num<node.root)
{
while(node.left!=null)
{
node=node.left;
//suppose we insert 56 that goes to left of 70 but after that we insert 60
if(num>node.root)
{
Node temp = new Node();
temp.root = num;
node.right = temp;

System.out.println(num + "" + "at right of" +node.root);

}


}
//some condition is required here.....
Node temp = new Node();
temp.root = num;
node.left = temp;
System.out.println(num + "" + "at left of" +node.root);


}







public static void main(String[] args) {
// TODO Auto-generated method stub

Node node = new Node();

node.root=70;
System.out.println("building tree with" + "" + node.root);
// node = node.insert(node, 70);
node.insertNode(node, 56);
/* node.insertNode(node, 45);
node.insertNode(node, 15);
node.insertNode(node, 16);
node.insertNode(node, 60);
node.insertNode(node, 80);
node.insertNode(node, 85);*/
/*node.insertNode(node, 45);
node.insertNode(node, 56);
node.insertNode(node, 16);
node.insertNode(node, 15);
node.insertNode(node, 60);
node.insertNode(node, 80);
node.insertNode(node, 85);*/
}

}
 
John Jai
Rancher
Posts: 1776
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Rebs,

Welcome to the Ranch

To get better help please TellTheDetails since ItDoesntWorkIsUseless

Can someone please make changes in code so that it works fine

I doubt any one will provide direct solution rather than help you find it... So please tell as what is your intention and where you are struck exactly.

I have added some Code Tags to your code and removed commented lines to make it look clearer.



 
rebps arora
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi John,

What i expect is:

If i call
node.insertNode(node, 56);
node.insertNode(node, 59);
node.insertNode(node, 45);
node.insertNode(node, 43);

The output should be:

56 at left of 70
59 at right of 56
45 at left of 56
43 at left of 45
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I prefer the recursive approach
 
rebps arora
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Campbell/John

Can you please help me in doing the same by non recursive method.


 
John Jai
Rancher
Posts: 1776
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you don't want to use a recursive method, you have to use a flag to check whether the addition of the new node is done.

The steps might not be clear. Let me take a try though.



Note that you have to implement code when the number is greater than the passed node's root...
 
sandeeprajsingh tandon
Ranch Hand
Posts: 80
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know its an old thread, but just wrote up the code as per the design pointers by some folks on this post. Hope it helps .
This code
- creates binary tree
- searches leaf nodes
- searches a node



The output is as such
1)
building tree with -> 70
Trying to insert 56
56 inserted to the left of 70
Trying to insert 59
found the node 56to the left of 70
Trying to insert 59
59 inserted to the right of 56
Trying to insert 45
found the node 56to the left of 70
Trying to insert 45
45 inserted to the left of 56
Trying to insert 43
found the node 56to the left of 70
Trying to insert 43
found the node 45to the left of 56
Trying to insert 43
43 inserted to the left of 45
Trying to insert 46
found the node 56to the left of 70
Trying to insert 46
found the node 45to the left of 56
Trying to insert 46
46 inserted to the right of 45
Trying to insert 100
100 inserted to the right of 70
Trying to insert 80
found the node 100to the right of 70
Trying to insert 80
80 inserted to the left of 100

2) Leaf Nodes are:
43
46
59
80

3)
Node 59 found at level 3 level below parent 56
Node 46 found at level 4 level below parent 45
 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A working solution at last
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just a few comments for cleaning up the design.

The names BinaryNode and root are misleading.

The name root is misleading because it does not actually represent the root of a tree in your code but rather the value of the node. The root of the tree would be a BinaryNode instance, not an int. See http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Terminologies_used_in_Trees.

The name BinaryNode is misleading because the logic in the class is actually that for a BinaryTree. Binary Trees are made up of Nodes. Your design would be clearer if you renamed BinaryNode to BinaryTree and created a nested class called Node. Then your insertNode(BinaryNode node, int num) method can be changed to just insert(int value). Your static methods searchBinaryNode(..) and leafNodes can then be made into proper instance methods of the BinaryTree class. As you have written it now, the code in these static methods break the encapsulation of the tree and its nodes. This kind of "code smell" is often called Inappropriate Intimacy.

Edit: when you refactor the static methods searchBinaryNode(..) and leafNodes(..) into proper instance methods of BinaryTree, their signatures would change to search(int value) and showLeaves() showLeafValues() or something like that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!