1

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?

2

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;
  • sounds smart. I'm going to be trying this soon. – Davide C Mar 31 '18 at 20:24
0

Recursion is possible indirectly:

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

You can also use a mapping instead of the array.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.