Are empty Binary Search Trees valid?

Question

I have two questions regarding binary search trees, both about empty trees.

1. Is an empty tree (null) valid?
2. Is a root node without children valid?

Answer 1

Exactly what an empty tree is of course depends on your implementation, as does the meaning of the word "valid", but in general I would say "yes" to both questions. The empty tree represents the case where the set of entities you are intersted in is empty, and the single node the case where the set contains one entity.

Answer 2

Yes, and yes.

Answer 3

Is an empty tree (null) valid?

There is no tree if it is empty. Hence the question of validity doesn't arise.

Is a root node without children valid?

Yes. That is a tee with only one element in it.

Answer 4

A single node with no children is certainly valid and according to Binary Tree Structure:

A (mutable) binary tree, BiTree, can be in an empty state or a non-empty state:

• When it is empty, it contains no data.
• When it is not empty, it contains a data object called the root element, and 2 distinct BiTree objects called the left subtree and the right subtree.

For completeness, this Wikipedia entry is a pretty useful summary of terminology and the like.

Answer 5

I think you're mixing together apples and oranges:

1. null is a value in some programming languages, and it is related upon the concrete representation of your implementation of the data structure
2. "Empty" is a property of the abstract data structure that we call "binary search tree"

Now, a tree is an ordered set: nothing more, nothing less. A set can be empty, of course! This means that, in your implementation, something similar to:

MyTree tree = null

represent an empty tree? Well, it depends upon your model. You can think, for ex., that an empty subtree should be represented by a node without value and with the references to the leafs nullified: in that model, a null pointer is meaningless from a logical perspective. But this is only one approach! The sentinel-based approach is a joy to program with, but it's memory expansive: you can then model empty nodes with just null. In that case, a null pointer can be an empty tree.