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

By Posted on

Problem

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 < current.key) ? current.left : current.right;
            }
            if (key < parent.key) {
                parent.setLeft(new Node(key));
            } else {
                parent.setRight(new Node(key));
            }
        }
    }

    public void insertAll(int... keys) {
        for (int key : keys) {
            insert(key);
        }
    }

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

    public boolean isComplete() {
        boolean result = true;
        if (root == null) {
            result = false;
        } else {
            Queue<Node> 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;
        }
    }
}

BinarySearchTreeTest 

package api.test;

import org.junit.Assert;
import org.junit.Test;

import api.BinarySearchTree;

public class BinarySearchTreeTest {

    @Test
    public void isCompleteRootOnly() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(12);
        Assert.assertTrue(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteRootAndLeft() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 4);
        Assert.assertTrue(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteRootLeftAndRight() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 7, 78);
        Assert.assertTrue(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteLastLevelFilled() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 7, 78, 1, 11, 45, 89);
        Assert.assertTrue(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteLastLevelNotFilledCompletely() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 7, 78, 1, 11, 45);
        Assert.assertTrue(binarySearchTree.isComplete());
    }

    @Test
    public void isNotCompleteLeftAbsent() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 7, 78, 1, 11, 89);
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isNotCompleteRightAbsent() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 7, 78, 1, 45, 89);
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteEmpty() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteLinkedListLeft() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(new int[] { 10, 9, 8 });
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteLinkedListRight() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(new int[] { 10, 11 });
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isCompleteLastButOneLevelNotFilled() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(new int[] { 10, 6, 15, 5, 8, 13, 4 });
        Assert.assertFalse(binarySearchTree.isComplete());
    }

    @Test
    public void isFullRoot() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(12);
        Assert.assertTrue(binarySearchTree.isFull());
    }

    @Test
    public void isFullRootAndTwoChildren() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 11, 13);
        Assert.assertTrue(binarySearchTree.isFull());
    }

    @Test
    public void isFull() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 10, 15, 1, 11, 13, 78);
        Assert.assertTrue(binarySearchTree.isFull());
    }

    @Test
    public void isFullRootAndLeft() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 10);
        Assert.assertFalse(binarySearchTree.isFull());
    }

    @Test
    public void isFullRootAndRight() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 13);
        Assert.assertFalse(binarySearchTree.isFull());
    }

    @Test
    public void isFullGapAtLastLevel() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 10, 15, 1, 13, 78);
        Assert.assertFalse(binarySearchTree.isFull());
    }

    @Test
    public void isFullGapAtLastLevel2() {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertAll(12, 10, 15, 1, 11, 78);
        Assert.assertFalse(binarySearchTree.isFull());
    }

}

I hope to hear some advice from you. I’d also be interested in hearing different approaches you would use to determine if the given binary search tree is complete. Especially, something not based on BFS.

Solution

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;.

Leave a Reply

Your email address will not be published. Required fields are marked *