Implementing Binary Search Tree in Java

Question

Here is a code I wrote for a binary search tree. Unfortunately, when I run it, it does not give th edesired output. Can someone tell me what I am doing wrong.

import java.util.ArrayList;


public class BinaryOrderedTree {
    BinaryOrderedTree left;
    BinaryOrderedTree right;
    static BinaryOrderedTree top;
    int key;
    static ArrayList<BinaryOrderedTree> values=new ArrayList<BinaryOrderedTree>();



    public int getKey(){
        return key;
    }


    public void setTop(BinaryOrderedTree top1){
        top=top1;
    }

    public BinaryOrderedTree getLeft(){
        return this.left;
    }

    public BinaryOrderedTree getRight(){
        return this.right;
    }

    public BinaryOrderedTree(int key){
        this.key=key;
    }

    public static BinaryOrderedTree addNode(BinaryOrderedTree node,BinaryOrderedTree top){
        if (node.getKey()<top.getKey()){
            if(top.left==null){
                System.out.println(node.getKey());
                System.out.println("left");
            top.left=node;
            }
            else{
                addNode(node,top.left);
            }
        }
        if(node.getKey()>top.getKey()){
            if(top.right==null){
                System.out.println(node.getKey());
                System.out.println("right");
                top.right=node;
            }
            else{
                addNode(node,top.right);
            }
        }
        return node;
    }

    public static BinaryOrderedTree searchNode(BinaryOrderedTree search, 
            BinaryOrderedTree top){
        if(search.getKey()==top.getKey()){
            return top;
        }
        else if(search.getKey()<top.getKey()){
            return searchNode(search,top.left);
        }
        else if(search.getKey()>top.getKey()){
            return searchNode(search,top.right);
        }
        return null;
    }

    public static BinaryOrderedTree traverse(BinaryOrderedTree top){
        values.add(top);
        System.out.println(top.getKey());
        if(top.left !=null)
        traverse(top.left);
        else if (top.right!=null)
        traverse(top.right);
        values.add(top.left);
        values.add(top.right);
        return top;
    }   

    public static void main(String[] args){
        BinaryOrderedTree top=new BinaryOrderedTree(7);
        BinaryOrderedTree firstNode=new BinaryOrderedTree(6);

        BinaryOrderedTree.addNode(firstNode,top);
        BinaryOrderedTree secondNode=new BinaryOrderedTree(4);
        BinaryOrderedTree.addNode(secondNode, top);
        BinaryOrderedTree thirdNode=new BinaryOrderedTree(8);
        BinaryOrderedTree.addNode(thirdNode, top);
        BinaryOrderedTree fourthNode=new BinaryOrderedTree(3);
        BinaryOrderedTree.addNode(fourthNode, top);
        BinaryOrderedTree.traverse(top);
//      System.out.println(BinaryOrderedTree.values);
    }
}

This is the output I get

    6
left
4
left
8
right
3
left
traversing pre-order
7
6
4
3

I can only assume that the nodes are being added correctly. However, it fails to show the node on the right of the top node and only traverses the left part. Could someone point out the flaw.

Markus Malkusch · Accepted Answer · 2014-02-26 15:50:53Z

1

Remove the else in your right traversal:

if(top.left !=null)
    traverse(top.left);
if (top.right!=null)
    traverse(top.right);

BTW your values might get filled strangely as well. values.add(top) is sufficient. Remove those values.add(top.left) and values.add(top.right).

BTW (one more) variable shadowing doesn't really help to understand your code.

answered Feb 26, 2014 at 15:50

Markus Malkusch

7,9382 gold badges40 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Implementing Binary Search Tree in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related