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

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<>();
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) {
}
if (node.right != null) {
}
}
}
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
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insertAll(new int[] { 10, 9, 8 });
Assert.assertFalse(binarySearchTree.isComplete());
}

@Test
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;`.