Clever Geek Handbook

Binary Search Insert - Root Remains Invalid

I'm new to Java, I want to create a binary search tree class with insertion and preorder traversal, but when I finish inserting, the root object remains empty and the compiler throws a NullPointerException during preorder traversal.

My node class:

class Node {
    int info;
    Node left;
    Node right;

    public Node() {
        info = 0;
        left = null;
        right = null;
    }

    Node(int x) {
        info = x;
        left = null;
        right = null;
    }
}

My search tree binary class:

public class BinarySearchTree {

    private Node root;

    public BinarySearchTree() {
        root = null;
    }

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

    public void insert(int x) {
        insertPrivate(root, x);
    }

    private void preorderPrivate(Node node) {
        if(node != null) {
            System.out.println(node.info);
            preorderPrivate(node.left);
            preorderPrivate(node.right);
        }
    }

    public void preorder() {
        preorderPrivate(root);
    }

    public static void main(String[] args) {
        BinarySearchTree t = new BinarySearchTree();
        t.insert(12);
        t.insert(13);
        t.preorder();
    }
}
+3


source to share


4 answers


The problem is misunderstanding the Java references as shown in this section of code.

  private void insertPrivate(Node node, int x) {
    if(node == null) {
        node = new Node(x);
    } 
    ....

Java references are passed by value to function arguments.

Let me give you an example for clarification.



Node root = new Node(x);
// root == Node(x);

doSomething(root);
// Pass Node(x) into function;

void doSomething(Node node) {
    // root == Node(x);
    // node == Node(x); 

    node = new Node(y); // This updates node but not root
    // root == Node(x);
    // node == Node(y);

}

You will have to restructure your program. One way would be to return insertPrivate

a Node

and assign that value to root. This is not the most efficient, but it will work.

public void insert(int x) {
    root = insertPrivate(root, x);
}

private Node insertPrivate(Node node, int x) {
    if(node == null) {
        node = new Node(x);
    } 
    else {
        if(x < node.info) {
            node.left = insertPrivate(node.left, x);
        } 
    else if (x > node.info) {
            node.right = insertPrivate(node.right, x);
        }
    }
    return node;
}
+2


source


Change insert(int x)

as follows:



public void insert(int x) {
    if (root == nul)
        root = new Node(x);
    else
        insertPrivate(root, x);
}
+1


source


Try: Node left = new Node (); Node right = new Node ();

0


source


You should somehow return the newly created node and assign it to the left or right of the parent node. Try the following:

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

And your public insert function should be:

public void insert(int x) {
    root = insertPrivate(root, x);
}

Also preorderPrivate needs a zero check:

private void preorderPrivate(Node node) {
    System.out.println(node.info);
    if (node.left != null)
        preorderPrivate(node.left);
    if (node.right != null)
        preorderPrivate(node.right);
}
0


source






More articles:


All Articles