Avoiding null referencing in recursive datastructure in C#-CodePudding

I am working with a Binary tree in C# and want to refactor the code, so none of the leafs in the tree is set to the null value.

Assuming we have the following class:

class Node
{
   int Data;
   Node Left;
   Node Right;
}

The classical constuctor for a node would be:

public Node(int Data)
{
  this.Data = Data;
  Left = null;
  Right = null;
}

But since I want to avoid null referencing, I wanted todo something similar to string.Empty, so my constructor would be something like:

public Node(int Data)
{
  this.Data = Data;
  Left = Node.Empty;
  Right = Node.Empty;
}


public Node()
{
  Data = int.MinValue;
  Left = Node.Empty;
  Right = Node.Empty;
}

I figured I could solve this by creating a static readonly variable called "Empty".

like so:

public static readonly Node Empty = new Node();

Tree traversal should in theory work, since instead of checking for if a leaf is equal to null, I would just have to check if a leaf is equal to the empty node, whichs means I would problaby also have to implement my own version of Equals right?

But I guess that would lead me in a bit of hot water, if I implemented the empty constructor like so:

The reason why I think it would land me into hot water, is that I believe the empty constructor would be called recursively.

If I set the leaf in the empty constructor alone to null I would get all kinds of warnings in Visual Studio, that a leaf might be null - even though it does never happen.

So what is the correct way if I want to avoid null referencing on a recursive data structure?

CodePudding user response：

Your default constructor should be private and assign this to your nodes:

private Node()
{
  this.Data = int.MinValue;
  Left = this;
  Right = this;
}

its only purpose is to create instance for the Empty property:

public static readonly Node Empty {get;} = new Node();

this way if you will achieve what you want but this construction opens you for stack overflow exceptions when you fail to check your nodes for being Empty in contrast to having null there and having null reference exception. I would argue that those warnings, that you are trying to remove by providing a non null value always, are there to help your protect your code and, annoying as theory are, they are helpful in writing code with that null in mind.