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.

Answer 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.