Binary Tree data structure

help
1

I would like to implement a BinaryTree data structure on Rust, but I have several questions:

  1. Shall I do only Node structure, or shall I do Node and BinaryTree structures separately? (I have seen both kinds of implementation)
  2. Shall there be a parent field in the Node struct?
  3. Which smart pointers should i use? In LeetCode implementation, Rc and RefCell are used, but i think that it is a good idea to use Box, Rc and RefCell, because Binary Tree and recursive Binary Tree operations can take a lof memory.
2

If you want to have such parent pointers, you will have to use Rc for the left_child and right_child fields and std::rc::Weak for the parent field, to avoid reference cycles.

Rc is already a pointer type—the reference-counted data is stored on the heap behind a layer of indirection. There's no need to add a second indirection by boxing it. If you don't need parent pointers, you could also use Box on its own.

1 Like
3

Wow, thank you! I have completely forgotten about that

4

LeetCode

check out this criticisim of leetcode's Rc<RefCell> for trees – https://github.com/pretzelhammer/rust-blog/blob/master/posts/learning-rust-in-2020.md#leetcode

Option<Rc<RefCell<Node>>> is overkill for tree links and Option<Box<Node>> works just as well and is much easier to work with

I wholeheartedly agree with the Box<Node> recommendation – it's the simplest way.

3 Likes
5

This is more a "what kind of API do you want to expose" question than a particularly-Rust question, to me.

If you're trying to make a container type (like a Vec or a BTreeMap), then I'd expect there to be a BinaryTree struct that I interact with as well as a private Node struct used internally that as the user of the container I wouldn't need to know about.

But it depends how you're trying to use it, and what your goals are in making the thing.

1 Like
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.