Hi,
I'm new to rust. I've gone through most of the book and rust by example, and all of rustlings. For some hands-on practice, I've been doing problems from https://www.techiedelight.com/
Some of them are quite easy. Then I decided to up my rust abilities and try one that involved building a binary tree. I was proud of myself when I made a "class" that could add nodes and print the contents. But the problem (Invert alternate levels of a perfect binary tree | Techie Delight) basically requires me do to a level order search of a mutable tree.
Questions:
- Is there a way to do this procedurally? I'd be ok learning unsafe if necessary.
- I want a procedural implementation, but for fun, it would be interesting to also do a functional one if it isn't too difficult, but I can't think of how to do it (it's been years since I've written a large program in a functional language).
Some approaches attempted or I've thought of:
- Do an in-place modification of the tree. I can't think of a way and keep the borrow-checker happy. The only way I can think of doing this is to have a mut ref to the nodes in a data structure queue/stack/vec/deque that is referenced in a loop. In my non-mut implementation (for printing the tree), I could use two vec's and it worked fine. For the mut version, it didn't like that. So I thought I would be clever and use a deque to keep everything in one place, but then it yelled at me when I referenced it one the second pass in the loop.
- Do a "copy-constructor". This is probably the more "functional" solution to the problem. However, I can't think of a way to create a node in a given spot in the tree.
Ideas:
- create a parent "pointer" to the parent node in the tree. Then I could easily walk the tree in a variety of ways. But, I don't know how to do this in Rust. Could I use an Rc and have essentially a doubly liked list between child and parent? I've heard rust Rc doesn't like loops.
Code:
// Solves: https://www.techiedelight.com/invert-alternate-levels-perfect-binary-tree/
// This is a fairly advanced Rust exercise (for me)
// Good reference for contstant tree data structures in Rust:
// https://endler.dev/2017/boxes-and-trees/
// Good reference for dynamic data structures:
// https://rust-unofficial.github.io/too-many-lists/
use std::mem;
struct BinTree {
value:i32,
left: Option<Box<BinTree>>,
right: Option<Box<BinTree>>,
}
impl BinTree {
//#![allow(dead_code)]
fn new(value:i32) -> BinTree {
BinTree {
value: value,
left: None,
right: None,
}
}
// add a value to the BinTree. The value will be added to the tree as a Binary Search Tree.
// If all values are added using this method, then the tree will be a correct BST.
fn add_sorted(&mut self, new_value:i32) {
if new_value < self.value {
// add left
match self.left {
Some(_) => {
// https://rust-unofficial.github.io/too-many-lists/second-peek.html
self.left.as_mut().map(|node| {
node.add_sorted(new_value);
});
}
None => self.left = Some(Box::new(BinTree::new(new_value))),
}
} else {
// add right
match self.right {
Some(_) => {
self.right.as_mut().map(|node| {
node.add_sorted(new_value);
});
}
None => self.right = Some(Box::new(BinTree::new(new_value))),
}
}
}
// print the tree in a nice level-order traversal.
fn pretty_print(&self) {
// TODO: implement Display? or the Debug display?
let mut current_level = 0;
println!("(note: nodes are not spaced and do not line up with levels)");
print!("{}: ", current_level);
for node in self {
if node.level > current_level {
current_level = node.level;
print!("\n{}: ", node.level);
}
if node.has_left_child {
print!("/");
}
print!("{}", node.value);
if node.has_right_child {
print!("\\");
}
print!(" ");
}
println!("");
}
//fn swap_children_nodes(&mut self) {
//mem::swap(&mut self.left, &mut self.right);
//}
// WRONG implementation. Doesn't solve problem correctly.
// But it compiles and runs well.
// fn invert_alternating_levels(&mut self, level: u32) {
// self.swap_children_nodes();
//
// // Using Option to get a mutable reference so we can call
// // our recursive function.
// self.left.as_mut().map(|node| {
// node.invert_alternating_levels(level+1);
// });
// self.right.as_mut().map(|node| {
// node.invert_alternating_levels(level+1);
// });
// }
// can I do a mutable level order traversal?? Attempt 5 or 6 now...
// I think the trick is to put the data into a single data structure,
// keep the data structure internal to the function, and use indexes
// instead of iterators. The indexes return Option, which allow
// mutable access.
#[deprecated()]
#[allow(dead_code)]
fn invert_alternating_levels(&mut self) {
let mut _level = 0;
let mut data: std::collections::VecDeque<&mut BinTree> = std::collections::VecDeque::new();
let mut num_current: usize = 0;
let mut num_next: usize = 0;
data.push_front(self);
num_current += 1;
while num_current > 0 {
// no iterators; this is intentional
for i in (std::ops::Range {start:0, end: num_current}) {
data[i].value = 1;
data[i].left.as_mut().map(|_child| {
// Can't call due to borrow checker!!
//data.push_back(child);
});
unimplemented!();
}
while num_current > 0 {
data.pop_front();
unimplemented!();
}
num_current = num_next;
num_next = 0;
_level += 1;
}
}
// attempt 6 or 7. Do a non-mutable level order traversal just
// like pretty_print() then return a new tree with the correct format.
// I wish I could to a in-place change of the current tree, but I
// couldn't figure out how. This has the same O() runtime and only
// a constant amount of extra memory, but it feels unnecessary.
#[deprecated()]
#[allow(dead_code)]
fn create_tree_with_inverted_alternating_levels(&self) -> Self {
let mut _level = 0;
let mut current_level = Vec::new();
let mut next_level = Vec::new();
current_level.push(self);
while current_level.len() > 0 {
for node in current_level.iter() {
// THE PROBLEM WITH THIS CODE:
// I have no idea how to force the construction
// of the new tree in the correct layout...
if let Some(left_child) = &node.left {
next_level.push(&**left_child);
}
if let Some(right_child) = &node.right {
next_level.push(&**right_child);
}
}
current_level.clear();
mem::swap(&mut current_level, &mut next_level);
_level += 1;
}
let b = BinTree::new(self.value);
b
}
}
#[allow(dead_code)]
#[derive(Debug)]
// This is the type currently returned by BinTree iterator.
// Maybe I should be returning actual BinTree, but this is fine for experimentation.
// A mut iterator should point to the actual thing.
struct LevelOrderSearcherData {
level: u32,
has_left_child: bool,
has_right_child: bool,
value: i32,
}
#[allow(dead_code)]
struct LevelOrderSearcher {
data: Vec<LevelOrderSearcherData>,
}
#[allow(dead_code)]
impl LevelOrderSearcher {
// perform level order search and put data into a vector which can be iterated through.
fn new(root: &BinTree) -> Self {
let mut data: Vec<LevelOrderSearcherData> = Vec::<LevelOrderSearcherData>::new();
let mut level = 0;
let mut current_level = Vec::new();
let mut next_level = Vec::new();
current_level.push(root);
while current_level.len() > 0 {
for node in current_level.iter() {
let d = LevelOrderSearcherData {
level: level,
has_left_child: node.left.is_some(),
has_right_child: node.right.is_some(),
value: node.value,
};
data.push(d);
if let Some(left_child) = &node.left {
next_level.push(&**left_child); // added * and & until compiler was happy. I almost understand what is going on.
}
if let Some(right_child) = &node.right {
next_level.push(&**right_child);
}
}
current_level.clear();
mem::swap(&mut current_level, &mut next_level);
level += 1;
}
Self {
data: data,
}
}
}
impl IntoIterator for BinTree {
type Item = LevelOrderSearcherData;
type IntoIter = std::vec::IntoIter<Self::Item>;
// iterates over the items, moving them into the new scope
fn into_iter(self) -> Self::IntoIter {
let level_order_searcher = LevelOrderSearcher::new(&self);
level_order_searcher.data.into_iter()
}
}
impl IntoIterator for &BinTree {
type Item = LevelOrderSearcherData;
type IntoIter = std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
let level_order_searcher = LevelOrderSearcher::new(self);
level_order_searcher.data.into_iter()
}
}
fn main() {
// create a perfect sorted tree
let mut bin_tree = BinTree::new(8);
bin_tree.add_sorted(4);
bin_tree.add_sorted(2);
bin_tree.add_sorted(1);
bin_tree.add_sorted(3);
bin_tree.add_sorted(6);
bin_tree.add_sorted(5);
bin_tree.add_sorted(7);
bin_tree.add_sorted(12);
bin_tree.add_sorted(10);
bin_tree.add_sorted(9);
bin_tree.add_sorted(11);
bin_tree.add_sorted(14);
bin_tree.add_sorted(13);
bin_tree.add_sorted(15);
bin_tree.pretty_print();
println!("Hello, world!");
}