It's possible (and practical!) if you allocate nodes in a List<T> and use indices instead of pointers. Then you can use bit 0 to encode the colour. Using bit 0

It's possible (and practical!) if you allocate nodes in a List<T> and use indices instead of pointers. Then you can use bit 0 to encode the colour. Using bit 0 instead of sign bit gives the advantage of branch-free code to retrieve the child index (always shift right by one).