CODEWITHSUNDEEP
java
dmetal23
dmetal23

Reputation: 141

Adding and generating a binary search tree

I'm having a bit of trouble figuring out how to add or insert Nodes to my binary search tree. At the moment I have the following code: 

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root;  
            while(...) { //not sure what to check
                if(v < m.value)
                    m = m.left;
                else
                    m = m.right;
            }
            if(...) //not sure what to check
                m.left = n;
            else
                m.right = n; 

        }   
    }

Then I also would like to generate n number of Nodes within a certain range. I know how to do this for arrays, but I'm not sure how to go about it for nodes in a BST. 

public void generate(int n, int range) {

  }

Upvotes: 0

Views: 94

Answers (3)

boxed__l
boxed__l

Reputation: 1336

Using your current approach, you will need an extra variable to track parent Node

public void add(int v) { 
        Node n = new Node(v); 
        if(root==null)
            root = n;   
        else {  
            Node m = root,k;  
            while(m!=null) {
                if(v < m.value){
                    k=m;
                    m = m.left;
                 }
                else if(v > m.value){
                    k=m;
                    m = m.right;
                 }else{
                    return; //v already exists
                 }
            }
            if(v < k.value)
                k.left=n;
            else
                k.right=n;
        }   
    }

For the second question about ranges, as DrYap pointed out, generate numbers within a range and for every number call add()

Upvotes: 0

Rich Schuler
Rich Schuler

Reputation: 41972

When adding a value to a BST you transverse the tree until you find an empty spot for it and insert a new node at that spot.

First we start with the degenerate case. I.e., there are no nodes and the root is null / empty.

Pseudocode:

if root is null then
    root = new node(value);
    return;
end if

So, all we are doing here is building the root node of the tree. It contains no leaf nodes.

All subsequent inserts now require us to transverse the tree.

So first we need a starting point which will be the root node. Then we also need to know if we have reached an empty spot where we can insert our new value into the tree. This requires keeping track of two variables; one to hold the current node we are examining and one to hold the parent of that node.

Psuedocode:

# initialize tracking variables.
checkNode = root;
parentNode = checkNode;

while checkNode is null do
    parent = checkNode; # want to save this for when we find a spot to store our new value
    if valueOf(checkNode) equals value then return # the value is already stored

    if value < valueOf(checkNode) then
        # the new value is less than the value stored in this node so continue down the left branch
        checkNode = checkNode.left 
    else 
        checkNode = checkNode.right # otherwise continue down the right branch
end while

# at this point checkNode will be null and parent will be set to a node that can store a new node with our value.

if value < valueOf(parent) then
     parent.left = node(value) # store a new node in the left of the found parent node
else 
     parent.right = node(value)

What we are doing is transversing down the tree comparing the value to be added to the value of the node we are checking. We are also keeping track of the parent of the node we are checking since this is where we are going to eventually end up inserting our new node. This is because we end our search when checkNode is null.

Upvotes: 0

DrYap
DrYap

Reputation: 6647

When you are inserting into the binary tree you want to go until you find a node which doesn't have the corresponding child. You then insert the new node in that position.

As for filling with numbers from a range, you generate them the same way you would for the array but instead of inserting into the array you can you add method.

Upvotes: 1

Related Questions