Binary Search Tree’s add method in Java

Tags: ,



I have a piece of code for inserting a node to Binary Search Tree in Java like:

public class BST {
private Node head;

public BST() {
    this.head = null;
}

public void add(int data, Node head) {
    if (head == null)
        head = new Node(data);
    else {
        if (data < head.data)
            add(data, head.left);
        else
            add(data, head.right);
    }
}

public void add(int data) {
    add(data, this.head);
}

public void preOrder(Node head) {
    if (head != null) {
        System.out.print(head.data + " ");
        preOrder(head.left);
        preOrder(head.right);
    }
}

public void preOrder() {
    preOrder(this.head);
}

public static void main(String[] args) {
    BST bst = new BST();
    for (int i = 0; i < 10; i++) {
        bst.add(i);
    }
    bst.preOrder();
}
}

Why doesn’t my information print when I run the program? Thank you for answering my question!!

Answer

You don’t update the left/right pointers when the recursion returns. Also, the local variable head is different from the instance variable. Hence, the new nodes you create are thrown away when the method returns.

Here is one way to do it.

The private add method returns the updated node which gets (re-)assigned when the recursion returns.

private Node add(int data, Node node) {
    if (node == null)
        return new Node(data);
    else {
        if (data < node.data)
            node.left = add(data, node.left);
        else
            node.right = add(data, node.right);
    }
   return node;
}

public void add(int data) {
    this.head = add(data, this.head);
}


Source: stackoverflow