Recursive struct in solidity

Question

I'm trying to implement a binary tree in solidity.

struct BTree{
  uint x;
  BTree lesser;
  BTree greater;
  bool    nil;
}

Just realized that this is not possible as struct definition can't be recursive. Is there any work around possible to achieve my goal?

Answer 1

I just wrote a blog post about doubly linked lists that should help: https://programtheblockchain.com/posts/2018/03/30/storage-patterns-doubly-linked-list/.

You can't have recursive structs, and there are no pointers, so you sort of have to make your own. Add each node to an array and use the index in the array as a "pointer." Something like this:

struct BTree {
    uint x;
    uint lesser;   // an index into btrees array
    uint greater;  // ditto
    bool nil;
}
BTree[] btrees;

Answer 2

Recursion is possible indirectly:

struct BTree {
  uint x;
  BTree[] children;
  bool nil;
}

You can also use a mapping instead of the array.