Given a binary search tree determine if it's complete and if it's full

Here is the code of my binary search tree and a few unit tests.

BinarySearchTree

package api;

import java.util.ArrayDeque;
import java.util.Queue;

public class BinarySearchTree {

    private Node root;

    public void insert(int key) {
        if (root == null) {
            root = new Node(key);
        } else {
            Node parent = null;
            Node current = root;
            while (current != null) {
                parent = current;
                current = (key  nodes = new ArrayDeque<>();
            nodes.add(root);
            boolean mustBeLeaf = false;
            while (!nodes.isEmpty()) {
                Node node = nodes.remove();
                if (mustBeLeaf) {
                    if (isLeaf(node)) {
                        continue;
                    } else {
                        result = false;
                        break;
                    }
                }
                if (node.right == null) {
                    mustBeLeaf = true;
                } else if (node.left == null) {
                    result = false;
                    break;
                }

                if (node.left != null) {
                    nodes.add(node.left);
                }
                if (node.right != null) {
                    nodes.add(node.right);
                }
            }
        }
        return result;
    }

    private boolean isLeaf(Node node) {
        return node.left == null && node.right == null;
    }

    public boolean isFull() {
        return isFull(root);
    }

    private static class Node {

        int key;
        Node left;
        Node right;

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

        @Override
        public String toString() {
            return Integer.toString(key);
        }

        void setLeft(Node left) {
            this.left = left;
        }

        void setRight(Node right) {
            this.right = right;
        }
    }
}

BinarySearchTr

Keep it simple

You should live by the KISS principle.

private boolean isFull(Node node) {
    if (node == null) {
        return true;
    }
    return !(node.left == null ^ node.right == null) && isFull(node.left) && isFull(node.right);
}

The use of the excusive or ^ together with the negation makes it hard to read what is going on. Some already have trouble with ^ alone, so adding ! complicates it more. You could replace !(node.left == null ^ node.right == null) with (node.left == null) == (node.right == null), but it is not necessarily clearer.

There's a better way to express this. First of all, I don't see why a null node would be a full node, since it isn't a node to begin with. This is also what isComplete is doing (returning false for a null node), so this joins the next point of being consistent. Going back to the description of a full node, it is when a node has either 0 or 2 children that are full.

• When the node is null, there is no node so it cannot be full.

• Has 0 children. This is clearly expressed by being a leaf node, and there is already a method for that we can reuse: isLeaf(node).

• Has 2 children. In this case, both left and right must be full.

This codes in:

private boolean isFull(Node node) {
    return node != null && (isLeaf(node) || isFull(node.left) && isFull(node.right));
}

or, if you prefer,

private boolean isFull(Node node) {
    if (node == null) {
        return false;
    }
    return isLeaf(node) || isFull(node.left) && isFull(node.right);
}

All tests still pass after that.

Be consistent

isFull is a method that implements early-returns; so you might as well do the same for isComplete. Instead of having a result variable, just return the result directly. For example:

boolean result = true;
if (root == null) {
    result = false;
} else {
    // ...
}
return result;

can be written as

if (root == null) {
    return false;
}
// ...

This removes one level of indentation and makes the method a little bit clearer. The same can be said for

if (mustBeLeaf) {
    if (isLeaf(node)) {
        continue;
    } else {
        result = false;
        break;
    }
}

which, in this case (because the break breaks from the single while loop), is simply

if (mustBeLeaf && !isLeaf(node)) {
    return false;
}

The continue; is redundant, as the rest of the code handles this case fine: when it is a leaf, both left and right will be null, so that nothing is added to the queue anyway later (thanks to the null-checks).

Finally, the method would end with return true;.

StackExchange Code Review Q#151953, answer score: 4