Skip to main content
More about objections to while(true)
Source Link
200_success
  • 144.2k
  • 22
  • 188
  • 473

There is nothing wrong withare two common objections to while (true): one invalid concern about efficiency, and one legitimate concern about style.

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

As previously mentioned, there is another problem with while (true), which is that it keeps the reader in suspense. Most programs are not intended to run in an infinite loop. Therefore, when you see while (true), you immediately suspect that something within the loop must eventually cause it to terminate: a break, a return, or an exception. Therefore, whenever you feel the urge to write while (true), it's always worthwhile to think about whether it is possible to restructure the code such that the termination condition can be expressed in the loop header, rather than buried in the loop body. In many instances, it is possible, but here, I think that my proposal is already optimal.

There is nothing wrong with while (true).

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

There are two common objections to while (true): one invalid concern about efficiency, and one legitimate concern about style.

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

As previously mentioned, there is another problem with while (true), which is that it keeps the reader in suspense. Most programs are not intended to run in an infinite loop. Therefore, when you see while (true), you immediately suspect that something within the loop must eventually cause it to terminate: a break, a return, or an exception. Therefore, whenever you feel the urge to write while (true), it's always worthwhile to think about whether it is possible to restructure the code such that the termination condition can be expressed in the loop header, rather than buried in the loop body. In many instances, it is possible, but here, I think that my proposal is already optimal.

Follow-up Q & A
Source Link
200_success
  • 144.2k
  • 22
  • 188
  • 473

Follow-Up Q & A

Not understanding your feedback - I suggest public void addElements(int[] elements) to be consistent with your addElement(int) method.

In Java, you use unboxed primitives most of the time. Boxed types are rare: generally they are only used in Collections (which can't store primitives) and when you want to store a value that might be null. An Integer[] array is therefore rather unnatural — it's neither an int[] nor a List<Integer>, both of which would be more likely to occur.

As regards to cleaning up addElement() I had few concerns

  1. while(true) is said to be bad

  2. more checks in your method (a) while(true) (b) null check (c) comparison, while my code does only 2 of them for most traversal part (a) null and (b) compare.

There is nothing wrong with while (true).

Many decades ago, simplistic C compilers might take while (true) literally, and generate code to load 1 into a register, check whether the register was non-zero, and execute a conditional jump. Modern C compilers and all Java compilers are smart enough to handle while (true) efficiently, generating nothing but an unconditional goto at the end of the loop. You can verify this by inspecting the bytecode:

$ cat WhileTrue.java
public class WhileTrue {
    private WhileTrue() {}  // Suppress default constructor

    public static void main(String[] args) {
        System.out.println("Before while loop");
        while (true) {
            System.out.println("In while loop");
        }
        // Compiler would detect this as unreachable
        // System.out.println("After while loop");
    }
}

$ javap -c WhileTrue
Compiled from "WhileTrue.java"
public class WhileTrue extends java.lang.Object{
public static void main(java.lang.String[]);
  Code:
   0:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:   ldc #3; //String Before while loop
   5:   invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   8:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   11:  ldc #5; //String In while loop
   13:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   16:  goto    8

}

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

Follow-Up Q & A

Not understanding your feedback - I suggest public void addElements(int[] elements) to be consistent with your addElement(int) method.

In Java, you use unboxed primitives most of the time. Boxed types are rare: generally they are only used in Collections (which can't store primitives) and when you want to store a value that might be null. An Integer[] array is therefore rather unnatural — it's neither an int[] nor a List<Integer>, both of which would be more likely to occur.

As regards to cleaning up addElement() I had few concerns

  1. while(true) is said to be bad

  2. more checks in your method (a) while(true) (b) null check (c) comparison, while my code does only 2 of them for most traversal part (a) null and (b) compare.

There is nothing wrong with while (true).

Many decades ago, simplistic C compilers might take while (true) literally, and generate code to load 1 into a register, check whether the register was non-zero, and execute a conditional jump. Modern C compilers and all Java compilers are smart enough to handle while (true) efficiently, generating nothing but an unconditional goto at the end of the loop. You can verify this by inspecting the bytecode:

$ cat WhileTrue.java
public class WhileTrue {
    private WhileTrue() {}  // Suppress default constructor

    public static void main(String[] args) {
        System.out.println("Before while loop");
        while (true) {
            System.out.println("In while loop");
        }
        // Compiler would detect this as unreachable
        // System.out.println("After while loop");
    }
}

$ javap -c WhileTrue
Compiled from "WhileTrue.java"
public class WhileTrue extends java.lang.Object{
public static void main(java.lang.String[]);
  Code:
   0:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:   ldc #3; //String Before while loop
   5:   invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   8:   getstatic   #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   11:  ldc #5; //String In while loop
   13:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   16:  goto    8

}

That means that your second objection is invalid, since while (true) is not a check. In fact, your original version had more conditionals since you had to decide which side to append to after exiting the loop.

Source Link
200_success
  • 144.2k
  • 22
  • 188
  • 473

Most of the code is pretty good!

I find your interface a bit weird. Instead of public void makeBinarySearchTree(Integer[] a), I suggest public void addElements(int[] elements) to be consistent with your addElement(int) method. There's no need to tell everyone that you're making a binary search tree, since that information is encoded into your class name already.

You might want to generalize the code to handle any Comparable, not just ints. You would get more flexibility for little additional effort.

Instead of throwing IllegalArgumentException, I would throw NoSuchElementException. In fact, I would change doesExist() to

private TreeNode find(TreeNode start, int element) {
    if (start == null) {
        throw new NoSuchElementException(Integer.toString(element));
    }
    if (element < start.item) {
        return find(start.left, element);
    }
    if (element > start.item) {
        return find(start.right, element);
    }
    // Assertion makes the code more readable
    assert element == start.item;
    return start;
}

That way, you can let the exception propagate up all the way, and it would tell you which of the two numbers passed to leastCommonAncestor() is missing.

Your addElement() is a bit repetitive and can be simplified:

public void addElement(int element) {
    // No matter what happens, we're going to attach this
    // new node somewhere.
    TreeNode newNode = new TreeNode(null, null, element);

    if (root == null) {
        root = newNode;
        return;  // Return early to avoid a layer of nesting
    }

    TreeNode node = root;
    while (true) {
        if (element <= node.item) {
            // Test for null before following the pointer.
            // That relieves you from having to keep track
            // of the parent node, and also avoids having
            // to decide again whether to attach to the
            // left or right.
            if (node.left == null) {
                node.left = newNode;
                return;
            }
            node = node.left;
        } else {
            if (node.right == null) {
                node.right = newNode;
                return;
            }
            node = node.right;
        }
    }
}