Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

# Binary Search Trees

kevin comario
Ranch Hand
Posts: 65
I have a question on binary search trees i am pretty much lost on how to add and remove: I am in an CS algorithms class but the book we have assigned is insufficent. Our professor has recomended another book by Thomas H. Cormen called "Introduction to Algorithms" the problem that i have right now is that i can't afford the book right now, so i have to make do with what I've got. So I've come to my favorite forum to ask for help.
Here is what I have been give:

Here is what I've done:

All I have done so far is extend BinarySearchTree and override the methods. I was hoping to get help on the add method. How should i go about it fromthe book i have i know that if the root is null then add to the root, if the root is not null then send the file left if <= and right if >= to root(how do i do this) then check to see if the left or right children are > or < and move acordingly changing so children into parents.
I personaly am very confused any help would be apprecitated.

James Chegwidden
Author
Ranch Hand
Posts: 201
As an instructor, I would look in your University Library for DS books. Usually the code will be written in somebook and usually you will have to translate it (ie. C to Java or C++ to Java) A lot of people have done binary trees so look it up.
Also, check search engines-you never know were you can find code to help

Greenhorn
Posts: 2
Hi,
As you might have learned, a BST is defined recursively, i.e., its definition is something like 'A Binary Tree is an entity storing some value, and having two associated trees (say, left tree and right tree). A BST is a Binary Tree having some convention between the value and left & child sub-trees. For example, value of left-subtree will always be less than the value of tree, and that of right-subtree will always be greater.'
Hope I'm making sense.
So, applying this, we can write a simple BST as below:

The same approach can be taken for 'remove' method. Also, as you might have guessed, incorporating level-count, returning sub-trees, maintaing node-count etc. are quite easier with this approach.
Downside - It uses recursion. I personally try to avoid it.
Practically, all your assignments can be smoothely done, as they don't need a huge amount of memory-storage for each recursive call.

kevin comario
Ranch Hand
Posts: 65
thanks for the help Aditya Jha but i am still very lost. You see i have to use this code specifically:

I'm having trouble using your code since my add method is your insert that takes a comparable object and mine takes an Integer object. and the nodes i have are from my BinaryTreeNode class. my question is, is the abstract class BinarySearchTree my tree? I understand the properties of a search tree but am lost in how to implement them in java. I was hoping to recieve help in my add method so i can see how its done.
one again thank you Aditya Jha but can you please give me a little more guidance.

William Barnes
Ranch Hand
Posts: 986
Random thoughts here:
> The code which Aditya posted is important. Do you know how to traverse a binay tree? That code shows you how.
> Your "add" method doesn't do anything if the tree is more than one layer deep.
> Your node is made up of two "pointers" and piece of data. In this case that data is an int.
> The add method takes a new piece of data (an int) and your job is to insert that into the tree. So you need to compare this new piece of data with the data already in your tree. These comparisons will let you know if you need to go left or right.

Norm Miller
Ranch Hand
Posts: 56
Kevin,
Back when I was trying to learn to algorithm stuff, "The Art of Computer Programming" by Donald Knuth was the Bible. I bought all three volumes available. I know he did a great job with trees of various kinds. You owe it to yourself to see if it is available in your college/university library. You don't have to buy every book you need. Once you understand the algorithm, the coding is a lot more obvious.

kevin comario
Ranch Hand
Posts: 65
Thanks for your help William Barnes and Miller, I went out and got the book Introduction to Algorithms by Thomas H. Cormen. The question i still have is how do i get my pointers to point. Thats where I'm having problems. That is why i was hoping for help using what has been given to me, so please forgive my ignorance in nodes I just really don't understand them.

James Chegwidden
Author
Ranch Hand
Posts: 201
What do you mean by "your pointers to point" there are no pointers in Java
Show us where in particular you are having a problem.

kevin comario
Ranch Hand
Posts: 65
well my problem mostly lies with these nodes:

I really dont get how to use this class how am i supposed to place integers in them if they hold nothing. I know java doesnt have pointers but how do i get them to link. Thats my question. like for instance if i wanted to set the left child of the root to ten
would i set root.left.value = 10? my question is how do this work how is it stored?
[ October 25, 2002: Message edited by: kevin comario ]

kevin comario
Ranch Hand
Posts: 65
Here are some of the changes i have made:

when i try to run this code i get a null pointer exception. I know it is becuase of the nodes, can someone please help.
[ October 26, 2002: Message edited by: kevin comario ]

William Barnes
Ranch Hand
Posts: 986
You are on the right track here.
But I don't think you have the idea of a binary tree yet. The tree is composed of "nodes", and in your case the node contains information about the nodes to the "left", "right", "parent", and an integer.
So the only real data in the node is the integer. The node is also a separate class, which makes OO sense.
So to "add" a node to a tree first you need to find where to add it, which you seem to be doing correctly. Than you need to create the node, and load it with data. That is the part you are missing. You need to create the node, hook it into the tree and set the int.
[ October 26, 2002: Message edited by: William Barnes ]

kevin comario
Ranch Hand
Posts: 65
Here Are the changes I have made:

I am still getting a logic error I think i messed-up on the add method because when i call my inorder method i get the wrong result. for instance in my test case i passed 2,1,3,5,7,8
my root should be 2 but i get 7, can somone please tell me what I'm doing wrong.

William Barnes
Ranch Hand
Posts: 986
Well a couple of things.

This is a bit redundent. Try this:

To know what is happening you want to add some print statements. I know this is a pain but it will help clear up what is actually happening. So code which outputs something like this:

And I don't know what your "inorder" code is doing. Almost all of it is commented out. Do you have code that is able to walk the entire tree?

William Barnes
Ranch Hand
Posts: 986
Looking at your "inorder" code again let me say this: you are not going to be able "cheat" by using a while loop to walk your tree. You are able to use a while loop to add nodes because you are only walking one branch of the tree. To walk the entire tree you will need to use recursion.

William Barnes
Ranch Hand
Posts: 986
C++ example code

William Barnes
Ranch Hand
Posts: 986
java code examples
Got all these with a quick google search.

kevin comario
Ranch Hand
Posts: 65
Thanks for the help i finally got it.