Is null a binary tree?

Question

So I have seen a few examples such as

How to validate a Binary Search Tree?

http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

They return 1, or true is a tree is null. Expanding questions a bit - assuming I had to find if TreeSmall is subtree of TreeBig, and my TreeSmall is null, should the return value of checkSubtree(smallTree) true or false ? A true indicates TreeSmall was a tree with value of null. This does not make sense to me.

Answer 1

In pure computer science, null is a valid binary tree. It is called an empty binary tree. Just like an empty set is still a valid set. Furthermore, a binary tree with only a single root node and no children is also valid (but not empty). See this Stack Overflow answer for more information.

In practical implementation, there are two ways to go about it though.

1. Assume that a valid binary tree must have at least one node and do not allow empty trees. Each node does not have to have children. All recursive methods on this tree do not descend to the level of null. Rather, they stop when they see that the left child or right child of a node is null. This implementation works as long as you don't pass null to any place where a tree is expected.

2. Assume that null is a valid binary tree (formally, just the empty tree). In this implementation, you first check if the pointer is null before doing any operations on it (like checking for left/right children, etc.) This implementation works for any pointer to a tree. You can freely pass null pointers to methods that are expecting a tree.

Both ways work. The second implementation has the advantage of flexibility. You can pass null to anything that expects a tree and it will not raise an exception. The first implementation has the advantage of not wasting time descending to "child nodes" that are null and you don't have to use null checks at the beginning of every function/method which operates on a node. You simply have to do null checks for the children instead.

Answer 2

That depends on the application and is a question of definition.

Edit:

For example Wikipedia "defines" a BST as follows:

In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree must each also be a binary search tree.
• There must be no duplicate nodes

Let's test those for null:

• left subtree doesn't exist, so there are no nodes violating this rule -> check
• similiar to first -> check
• if all this tests are passed this passes too, since both subtrees are null -> check
• of course there aren't duplicates -> check

So by this definition null is a valid BST. You could inverse this by also requiring "there must be one root node". Which doesn't affect any of the practical properties of a BST but might in an explicit application.

Answer 3

Ex falso sequitur quodlibet - since "null" is nothing at all, it can be interpreted to be anything. It is really a matter of design. Some people may claim that checkSubTree() should thrown something like an IllegalArgumentException in this case. Another approach would be to introduce a special kind of typed object or instance which represents an empty tree (cf. NullObjectPattern). Such a null-object would be a tree by all accounts, e.g. EmptyTree instanceof Tree, while null instanceof Tree would always be false.