4
\$\begingroup\$

I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion.
I am under the impression that while (true) is a bad practice, correct?

    while (true){
        if(n <currentNode.data){
            if (currentNode.left == null){
                currentNode.left = new node(n);
                break;
            }else{
                currentNode = currentNode.left;
            }
        }else 
            if (currentNode.right == null) {
                currentNode.right = new node(n);
                break;
            } else{
                currentNode = currentNode.right;
            }
    }

and here is the whole code:

package graph;

public class BSearchTree {
    private node head = null;
    public BSearchTree(int [] entries){
        for (int a : entries){
            insert(a);
        }
    }
    public void insert(int n){
        if (head == null){
            head = new node(n);
            return;
        }
        node currentNode = head;
        while (true){
            if(n <currentNode.data){
                if (currentNode.left == null){
                    currentNode.left = new node(n);
                    break;
                }else{
                    currentNode = currentNode.left;
                }
            }else 
                if (currentNode.right == null) {
                    currentNode.right = new node(n);
                    break;
                } else{
                    currentNode = currentNode.right;
                }
        }

    }

    public static void main(String[] args) {
        BSearchTree bst = new BSearchTree(new int[]{2,4,1,5});  
        System.out.println(bst.toString());
    }


    private class node {
        int data = -1;
        node left = null;
        node right = null;

        public node(int n){
            data = n;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ while(true)just causes an infinite loop, is that what you want to do? If so, to me anyway, that's the simplest way to do it. \$\endgroup\$ – user152925 Nov 9 '17 at 17:45
  • \$\begingroup\$ @no, I am processing a finite stream in a seemingly infinite fashion, I dont want that. \$\endgroup\$ – Waterfr Villa Nov 9 '17 at 17:55
  • \$\begingroup\$ I wouldn't say a while (true) ... break is necessarily bad practice. It can be nice then do while, and you don't always want to declare a boolean for no reason. Some consider break a form of goto (some also pre-function end returns gotos, but it's really just context-dependent), but sometimes it's clearer and more efficient than any alternatives. \$\endgroup\$ – Graham Nov 5 '18 at 5:05
0
\$\begingroup\$

(Just checking - you want your BST to be allowed to contain duplicates? That's what your current code does.)

Edit: After fixing some mistakes kindly pointed out by @vnp, here is an implementation of insert:

    public void insert(int n) {
        final boolean RIGHT = true;
        final boolean LEFT = false;

        node previousNode = null;
        boolean previousDirection = LEFT; // arbitrary
        node currentNode = head;

        while (currentNode != null) {
            previousNode = currentNode;
            if (n > currentNode.data) {
                currentNode = currentNode.right;
                previousDirection = RIGHT;
            } else {
                currentNode = currentNode.left;
                previousDirection = LEFT;
            }
        }

        if (previousNode == null) {
            head = new node(n);
        } else if (previousDirection == LEFT) {
            previousNode.left = new node(n);
        } else {
            previousNode.right = new node(n);
        }
    }

This avoids using while(true) and break; and uses more shallow if statements, which I think makes it marginally easier to follow.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't see node.next defined anywhere. There are node.left and node.right. \$\endgroup\$ – vnp Nov 9 '17 at 21:28
  • \$\begingroup\$ @vnp Good point! I'm missing this. How about also storing a boolean previousDirection at each step, and using this to determine whether to go right or left? (That means declaring private final static boolean RIGHT = true; private final static boolean LEFT = false; at the start.) \$\endgroup\$ – ArbitraryGenera Nov 9 '17 at 21:37
  • 1
    \$\begingroup\$ Then I see no benefits (suggested implementation would be helpful). BTW, those RIGHT and LEFT do not belong to the class; they are local to insert. \$\endgroup\$ – vnp Nov 9 '17 at 21:43
  • \$\begingroup\$ @vnp thanks! I've provided an implementation - it's definitely arguable that this implementation is no better! \$\endgroup\$ – ArbitraryGenera Nov 9 '17 at 22:49
  • \$\begingroup\$ Is it also easier to understand? I mean compared to my solution? \$\endgroup\$ – Waterfr Villa Nov 10 '17 at 16:49
0
\$\begingroup\$

private class node

I suggest you declare it as

private static final class BinarySearchTreeNode<E> {

    E datum;
    BinarySearchTreeNode<E> left;
    BinarySearchTreeNode<E> right;

    BinarySearchTreeNode(E datum) {
        this.datum = datum;
    }
}

Above, private tells Java that the class is not accessible outside of enclosing BSearchTree, static removes an implicit reference to BSearchTree from each node object, final tells Java that it is not possible to inherit from node. Finally, I would go verbose here and rename node to BinarySearchTreeNode.

Superfluous access modifier

private class node {
    int data = -1;
    node left = null;
    node right = null;

    public node(int n){ // 'public' does not buy you here anything.
        data = n;
    }
}

Adding generics

Going for generic binary search tree is not much harder, so, as a further exercise, I suggest to add generics (see the Summa summarum.)

Miscellaneous advice

I suggest you rename head to root.

Package name

graph is too short and too uninformative name for you code's package. Consider renaming to, say, net.villa.util.

Summa summarum

Combining all the advices above, I came with this proposition:

package net.villa.util;

public class BinarySearchTree<E extends Comparable<? super E>> {

    private BinarySearchTreeNode<E> root;

    public void insert(E value){
        if (root == null) {
            root = new BinarySearchTreeNode<>(value);
            return;
        }

        BinarySearchTreeNode<E> node = root;
        BinarySearchTreeNode<E> parent = null;
        int cmp = 0;

        while (node != null) {
            cmp = value.compareTo(node.datum);

            if (cmp == 0) {
                // The 'value' is already in this tree.
                return;
            }

            parent = node;

            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            }
        }

        BinarySearchTreeNode<E> newNode = new BinarySearchTreeNode<>(value);

        if (cmp < 0) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        toStringImpl(stringBuilder, root, new Separator(""));
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    private static final class Separator {
        String separator;

        Separator(String separator) {
            this.separator = separator;
        }
    }

    private static <E> void toStringImpl(StringBuilder stringBuilder,
                                         BinarySearchTreeNode<E> node,
                                         Separator separator) {
        if (node.left != null) {
            toStringImpl(stringBuilder, node.left, separator);
        }

        stringBuilder.append(separator.separator);
        stringBuilder.append(node.datum);

        if (separator.separator.equals("")) {
            separator.separator = ", ";
        }

        if (node.right != null) {
            toStringImpl(stringBuilder, node.right, separator);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.insert(3);
        bst.insert(1);
        bst.insert(0);
        bst.insert(2);
        bst.insert(5);
        bst.insert(4);
        bst.insert(7);  
        System.out.println(bst.toString());
    }

    private static final class BinarySearchTreeNode<E> {

        E datum;
        BinarySearchTreeNode<E> left;
        BinarySearchTreeNode<E> right;

        BinarySearchTreeNode(E datum) {
            this.datum = datum;
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.