CODEWITHSUNDEEP
javabinary-search-tree
Abhijeet Mohanty
Abhijeet Mohanty

Reputation: 344

Incorrect output : Binary Search Tree implementation using Java

I am new to Java and I have been trying to implement a BST but the program outputs only the last inserted value. Am I going wrong with respect to what my root_node is pointing at? Below are my source codes for Tree.java and Node.java.

Tree.java

public class Tree {

    private Node root_node;

    public void Tree() {
        this.root_node = null;
    }

    public void insertNode (int value) {

        root_node = insertNode(root_node, value);
    }

    public Node insertNode (Node node, int insert_value) {

        if (node == null) {
            return (new Node(insert_value));
        }
        else {
            if (node.getNodeValue() < insert_value)
                node = insertNode(node.getLeftNode(), insert_value);
            else
                node = insertNode(node.getRightNode(), insert_value);

            return (node);
        }
    }

    public void printNode () {

        printNode(root_node);
    }

    public void printNode (Node node) {

        if (node != null){

            System.out.print(node.getNodeValue() + " ");

            printNode(node.getLeftNode());
            printNode(node.getRightNode());
        }
    }

    public static void main(String[] args) {

        Tree tree = new Tree();

        tree.insertNode(54);
        tree.insertNode(87);
        tree.insertNode(11);
        tree.insertNode(25);

        tree.printNode();
    }
}

Node.java

public class Node {

    private int node_value;

    private Node left_node, right_node;

    public Node(int root_value) {

        this.node_value = root_value;

        this.left_node = null;
        this.right_node = null;

    }

    public int getNodeValue() { return (this.node_value); }

    public Node getLeftNode() { return (this.left_node); }

    public Node getRightNode() { return (this.right_node); }
}

The error is that my source code only displays the last inserted no. which is 25 in this case.

Upvotes: 0

Views: 34

Answers (3)

dabaicai
dabaicai

Reputation: 999

In you Tree class ,the mehtod public Node insertNode (Node node, int insert_value) is not correctly,shoude like this:

        if (node.getNodeValue() < insert_value) {
            Node left = insertNode(node.getLeftNode(), insert_value);
            node.left_node = left;
        }

        else {
            Node right = insertNode(node.getRightNode(), insert_value);
            node.right_node=right;
        }

you should save the new node which return by the insertNode into leftchild node field or rightchild node field in which current node,if not,the printNode will just print root node and return,because the root node's left or right child node is null.

Upvotes: 1

janos
janos

Reputation: 124646

The implementation of insertNode is incorrect. You always call this method with:

root_node = insertNode(root_node, value);

And then if you look at the method:

if (node == null) {
    return (new Node(insert_value));
}
else {
    if (node.getNodeValue() < insert_value)
        node = insertNode(node.getLeftNode(), insert_value);
    else
        node = insertNode(node.getRightNode(), insert_value);

    return (node);
}

On the first call, the first if condition will match, a new node will be created and assigned to root_node in the caller.

But then, in subsequent calls, what will happen? The first if doesn't match, so the else block will be taken. But then, both branches reassign the node parameter of the method. So the effects of the else method will remain inside the insertNode method, and so no other value will ever be added.

Aside from rewriting the insertNode method, you will need other changes too. For example, currently there is no way to set or modify the left and right nodes of a node. You will need to add some way for that, either by setters or constructors.

For example, with appropriate setters added, this will work:

  public Node insertNode(Node node, int insert_value) {
    if (node == null) {
      return new Node(insert_value);
    }
    if (node.getNodeValue() < insert_value) {
      node.setLeftNode(insertNode(node.getLeftNode(), insert_value));
    } else {
      node.setRightNode(insertNode(node.getRightNode(), insert_value));
    }
    return node;
  }

Upvotes: 1

Norbert
Norbert

Reputation: 6084

What seems to happen is that this errors out:

You create your root_node with the first call (should be called rootNode following java conventions). Then you call either getLeftNode or getRightNode, but those do not exist, so I guess they return null.

        if (node.getNodeValue() < insert_value)
            node = insertNode(node.getLeftNode(), insert_value);
        else
            node = insertNode(node.getRightNode(), insert_value);

returns null on the second call.

Now your root_node is null again, with as result that you only have the last inserted value, etc. So this seems to be the reason why your code only returns the last node value when you call print.

Upvotes: 1

Related Questions