# Binary Search Tree

• November 7th, 2009, 08:03 AM
Koren3
Binary Search Tree
Hello, I have to do Binary Search Tree. I found on internet a lot of versions, but i need it just simple. First time, I need help with method insert.
My code:
Code :

```public class BinarySearchTree { private Node root; private Node parent; private Node node;     public boolean isEmpty() { return root==null ; }   public void insert(int number) { if(root==null) { Node newNode = new Node(); newNode.setData(number); root=newNode; } }   public void remove(int) {   }   public boolean contains(int) { return; }     }```

Code :

```public class Node { private Node left; //left children private Node right; //right children private Node parent; private int data;     public void setLeft(Node left) { this.left=left; } public Node getLeft() { return left; }   public void setRight(Node right) { this.right=right; }   public Node getRight() { return right; }   public void setParent(Node parent) { this.parent=parent; }   public Node getParent() { return parent; }   public void setData(int data) { this.data=data; }   public int getData() { return data; } }```
• November 7th, 2009, 10:27 AM
copeg
Re: Binary Search Tree
The simplified textbook way of doing insert into a binary tree is to use recursion. Create a function that accepts a Node and (in your case) an int as parameters. Check if the node is null, if it is return a new node, if it is not, check the value against the current node data, if it is greater than perform insert on the right node and if it is less than perform insert on the left node. You initiate the insert by passing the root node as the parameter.
semi pseudo-code
Code :

```private Node insert(Node node, int data) { //insert code to check if node is null, if it is return a new node ...... //recursively go down the tree if ( node.getData() > data ) { node.setRight(insert( node.getRight(), data));//do insert on the right node } else { //...do the same as above for the the left node } return node; } public void insertData(int data) { root = insert(root, data); }```

Other functions, such as removal and traversal involve a similar type of code to move down the tree until you hit the node you want.
• November 7th, 2009, 10:43 AM
Koren3
Re: Binary Search Tree
Thank you but Donīt it do another way? Because I got UML diagram with methods and method insert look like insert (int).
UML diagram on picture: Imageshack - treeu
• November 7th, 2009, 11:05 AM
copeg
Re: Binary Search Tree
Quote:

Originally Posted by Koren3
Thank you but Donīt it do another way? Because I got UML diagram with methods and method insert look like insert (int).
UML diagram on picture: Imageshack - treeu

That's essentially what the insertData function is in the code above. Just rename the two functions to conform to the UML
• November 8th, 2009, 02:15 AM
Koren3
Re: Binary Search Tree
Ohh yes. Thank you.
I wrote this code:
Code :

```public boolean isEmpty() { return root==null ; }   private Node insertData(Node node, int data) { //insert code to check if node is null, if it is return a new node if (node==null) { return node; } //recursively go down the tree if ( node.getData() > data ) { node.setRight(insertData( node.getRight(), data));//do insert on the right node } else { node.setLeft(insertData(node.getLeft(), data));//do insert on the left node } return node; } public void insert(int data) { root = insertData(root, data); }```
Code :

```public class Main {     public static void main(String[] args) { BinarySearchTree b1 = new BinarySearchTree();   System.out.println(b1.isEmpty()); b1.insert(10); b1.insert(5); b1.insert(3); b1.insert(12); b1.insert(14); System.out.println(b1.isEmpty());   }   }```
But it write:
true
true
Where is the problem?
• November 8th, 2009, 10:00 AM
helloworld922
Re: Binary Search Tree
In you're insert method you need to check for a null root node. Then, if it is null, create a new node.
• November 10th, 2009, 01:41 PM
Koren3
Re: Binary Search Tree
I changed it but nothing...
Did you mean this?
Code :

```public class BinarySearchTree { private Node root; private Node parent; private Node node;     public boolean isEmpty() { return root==null ; }   private Node insertData(Node node, int data) { //insert code to check if node is null, if it is return a new node if (node==null) { return node; } //recursively go down the tree if ( node.getData() > data ) { node.setRight(insertData( node.getRight(), data));//do insert on the right node } else { node.setLeft(insertData(node.getLeft(), data));//do insert on the left node } return node; } public void insert(int data) { if (root==null) { root = insertData(root, data); } }```
• November 10th, 2009, 03:26 PM
helloworld922
Re: Binary Search Tree
no, like this:

Code :

```public void insert(int data) { if (root == null) { root = new Node(); // err, i'm not sure i know what you're node constructor looks like, but put it here } insertData(root, data); }```
• November 11th, 2009, 01:11 AM
Koren3
Re: Binary Search Tree
I changed it:
Code :

```public class BinarySearchTree { private Node root; private Node parent; private Node node;     public boolean isEmpty() { return root==null ; }   private Node insertData(Node node, int data) { //insert code to check if node is null, if it is return a new node if (node==null) { return node = new Node(); } //recursively go down the tree if ( node.getData() > data ) { node.setRight(insertData(node.getRight(), data));//do insert on the right node } else { node.setLeft(insertData(node.getLeft(), data));//do insert on the left node } return node; } public void insert(int data) { if (root==null) { root = new Node(); insertData(root, data); } insertData(root, data); }```
Class Node:
Code :

```public class Node { private Node left; //left children private Node right; //right children private Node parent; private int data;     public void setLeft(Node left) { this.left=left; } public Node getLeft() { return left; }   public void setRight(Node right) { this.right=right; }   public Node getRight() { return right; }   public void setParent(Node parent) { this.parent=parent; }   public Node getParent() { return parent; }   public void setData(int data) { this.data=data; }   public int getData() { return data; } }```

But something is wrong. picture Ddebuger: Imageshack - debuga
• November 12th, 2009, 08:27 AM
Koren3
Re: Binary Search Tree
Ok I solved it. Now i am trying do method remove.