CODEWITHSUNDEEP
javadata-structures
user3105226
user3105226

Reputation: 43

Simple binary search tree in Java

Here there is code for a simple BST in Java that keys are only int, but when I want to test it and use print() just root.key can be printed and root.right and root.left are null.

public class BST {

    private class Node {
        private int key;
        private Node left, right;

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

    private Node root;

    public BST(int key) {
        root = new Node(key);
    }

    public void insert(int key) {
        insert(root, key);
    }

    private void insert(Node x, int key) {
        if (x == null) {
            x = new Node(key);
        }
        if (key > x.key) {
            insert(x.right, key);
        } else if (key < x.key) {
            insert(x.left, key);
        } else {
            x.key = key;
        }
    }

    public void print() {
        print(root);
    }

    private void print(Node x) {
        System.out.print(x.key + " ");
        if (x.left != null)
            print(x.left);
        if (x.right != null)
            print(x.right);
    }
}

For example, when I insert 25, 9, 10, 30, 40 and call print() then it just prints 25.

Upvotes: 1

Views: 4160

Answers (1)

Niklas B.
Niklas B.

Reputation: 95358

x = new Node(key);

This assignment basically throws away the new Node, because x is just a local variable. You are not modifying the callers reference here, you are just modifying the local copy of the reference the caller gave you. What you could do is return the x and have the caller assign it:

x = insert(x, 3);

The insert would then look something like this:

private Node insert(Node x, int key) {
    if (x==null){
        return new Node(key);
    }
    if (key > x.key) {
        x.right = insert(x.right, key);
    }else if (key < x.key) {
        x.left = insert(x.left, key);
    }else{
        x.key = key;
    }
    return x;
}

Upvotes: 5

Related Questions