Do binary search trees have null children that are not shown?

Question

In every diagram of binary search trees that I have found it appears there are nodes that only have 1 child. Do these nodes actually have only one child or is there another null child that is not shown. For example, does 14 have a right null child that is not shown? This would make tree traversals make more sense.

Answer 1

Yes, whenever there aren't exactly 2 children, the references / pointers to the remaining children will contain null values (or whatever the equivalent of that is in whichever language it's implemented in).

So 14 will have a null right child, and 1, 4, 7 and 13 will have null left and right children.

I can only speak for a fairly small subset of languages, but you'll definitely need to have some sort of "points to nothing" concept, which these will contain.

---

The above assumes you have a structure similar to:

node
   node left
   node right
   type value

As an alternative to this representation (although I can't say I've ever seen this used for a binary tree - just presenting the possibility), you could also have an array of children, for example - a size 2 array means both left and right children, a size 1 array means only 1 child - you could perhaps have a flag indicating whether it's a left or right child (or, since it's a BST, you could just compare it to determine which it is), a size 0 array means no children. Note that this array needn't contain any null values.