Growing a (sorting) tree

by marco.p.v.vezzoli · March 17, 2024

Photo by Jared Subia on Unsplash In this post we will extend our binary tree using generics and trait constraint, and add a simple sorting algorithm based on depth first traverse.

Adding some fruit to our tree

In a previous post Growing a (binary) tree I described what a binary tree is and how to create one in Rust. To really have an useful tree we may want to add some content to the data structure. let’s start with something simple: each node can host a 32 bit integer

#[derive(Debug)]
pub struct BTree0 {
    pub left : Option<Box<BTree0>>,
    pub right : Option<Box<BTree0>>,
    pub content : i32,
}

Trees are often built with a recursive function call, i.e. a function which calls itself. Of course there should be some way to limit this calls in order to avoid infinite loops. Let’s start with a function which accepts two values:

a maximum possible depth of our tree
the current depth of the tree itself.

The level of each node will be stored in the node content.

fn main() {
    let test = add_level(1, 4);
    println!("Hello, world! {:?}", test);
}

fn add_level(current_level : i32, max_level : i32) -> BTree0 {
    // this expression is the value returned by this function
    BTree0 {
        left: (
            // also if blocks can return a value
            if current_level < max_level{
                // each call increases the current level until the maximum
                Some(Box::new(add_level(current_level + 1, max_level)))
            } else {
               None
            }
        ),
        right: (
            if current_level < max_level{
                Some(Box::new(add_level(current_level + 1, max_level)))
            } else {
               None
            }
        ),
        content: current_level
    }
}

In this code you can see an interesting idiom in Rust: each time the last eselement of a block is an expression, it is returned as a value. Please note that these expressions are not followed by a semicolon.

Adding nodes to our tree

Some times we might want to add new branches to our tree after we built it. An example is to create a binary tree for sorting: we first start with a single value in our root node:

as values are collected they will be eventually added to the tree: left node will have a value which is less than the parent, right node a value greater than the parent.

This requires quite a few Rust idioms

we need to create a mutable root in order to send mutable references to a function, this is needed to add new branches to our initial root
we need to access each node and possibly understand if it has any children: this will be done by using a pattern match on the Option enum.
we need to access some children node as a mutable reference; using the ref mut signature in the pattern match we can achieve this

fn main() {
    //this is the root node
    let mut test = BTree1{ left: None, right: None, content: 5 };
    add_element(& mut test, 2); // this will add a left branch
    add_element(& mut test, 4); // this will add a right branch on the left branch
    add_element(& mut test, 5); // this will be ignored
    add_element(& mut test, 6); // this will add a rigth branch
    println!("Hello, world! {:?}", test);
}

fn add_element(node: & mut BTree1, value: i32){
    if node.content == value{
        // if the value is already in the tree do nothing
        return;
    } else if node.content < value {
        // check the left side for smaller values
        match node.left {
            None => {
                node.left = Some(Box::new(
                    BTree1 { left: None, right :None, content: value}
                ));
            }
            // a tricky part: we need to tell the compiler to return a
            // mutable reference from this pattern match otherwise it
            // may try to move the ownership of the data (which we don't want)
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    } else {
        match node.right {
            None => {
                node.right = Some(Box::new(
                    BTree1 { left: None, right :None, content: value}
                ));
            }
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    }
}

Exploring the tree

we can extract the content of our tree in a way that shows it in order:

enter a node
if it has a left node enter the left node (back to point 1)
print the content of the current node
if it has a right node enter the right node (back to point 1)
return to the parent node

this sequence is called depth-first traversal of our binary tree. Before implementing this you may notice that the following expression appears three times:

BTree1 { left: None, right :None, content: value}

this creates a leaf node, i.e. a node with no children: it may deserve a function on its own:

fn make_leaf(value: i32) -> BTree1{
    BTree1 { left: None, right :None, content: value}
}

this is how the insertion code looks now using make_leaf:

fn add_element(node: & mut BTree1, value: i32){
    if node.content == value{
        // if the value is already in the tree do nothing
        return;
    } else if node.content > value {
        // check the left side for smaller values
        match node.left {
            None => {
                node.left = Some(Box::new(make_leaf(value)));
            }
            // a tricky part: we need to tell the compiler to return a
            // mutable reference from this pattern match otherwise it
            // may try to move the ownership of the data (which we don't want)
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    } else {
        match node.right {
            None => {
                node.right = Some(Box::new(make_leaf(value)));
            }
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    }
}

now let’s implement our traversal algorithm: we are only keep exploring when children are available so, instead of a pattern matching, an if let expression is enough

fn deep_traversal_print(node: & BTree1){
    if let Some(ref subnode) = node.left {
        deep_traversal_print(subnode);
    }
    print!("{} ",node.content);
    if let Some(ref subnode) = node.right {
        deep_traversal_print(subnode);
    }
}

We are all set! Also let’s use a loop to create our tree

fn main() {
    let mut test = make_leaf(5);
    for i in [4,3,5,6]{
        add_element(& mut test, i);
    }
    // this will print 3 4 5 6
    deep_traversal_print(& test);
}

Adding other Fruits

What if we want to have a tree with a different content: generics to the rescue! Generics is the Rust way to implement “parametric polymorphism”, i.e. create data structures and algorithms which accept a type as a parameter. This is how we can add a parameter T into our tree.

#[derive(Debug)]
pub struct BTree2<T> {
    pub left : Option<Box<BTree2<T>>>,
    pub right : Option<Box<BTree2<T>>>,
    pub content : T,
}

// a node can be created updating
// the function with the generic type T
fn make_leaf<T>(value: T) -> BTree2<T>{
    BTree2 { left: None, right :None, content: value}
}

Very nice. But what if we want to add elements and have them sorted into the tree as before? We need to define a “total ordering” in our unknown type T; Rust defines a trait for types with a total order Ord. So we need T to be acceptable only if it implements the Ord trait. This is called “generic contstraint”. Let’s see how implement this in Rust

// the constraint appears in the function definition
fn add_element<T: Ord>(node: & mut BTree2<T>, value: T){
    if node.content == value{
        return;
    } else if node.content > value {
        match node.left {
            None => {
                node.left = Some(Box::new(make_leaf(value)));
            }
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    } else {
        match node.right {
            None => {
                node.right = Some(Box::new(make_leaf(value)));
            }
            Some(ref mut subnode) => {
                add_element(subnode, value);
            }
        }
    }
}

And what if we want to print our data when we traverse the tree? We need to implement the std::fmt::Display trait

use std::fmt::Display;

fn deep_traversal_print<T: Display>(node: & BTree2<T>){
    if let Some(ref subnode) = node.left {
        deep_traversal_print(subnode);
    }
    print!("{} ",node.content);
    if let Some(ref subnode) = node.right {
        deep_traversal_print(subnode);
    }
}

Now we are ready to add more fruit: let’s see an example with str

fn main() {
    let mut test = make_leaf("orange");
    for i in ["banana","apple","orange","mango"]{
        add_element(& mut test, i);
    }
    // this will print 3 4 5 6
    deep_traversal_print(& test);
}

Growing a (sorting) tree

Adding some fruit to our tree

Adding nodes to our tree

Exploring the tree

Adding other Fruits

Like this:

Related

You may also like...

Growing a (sorting) tree

Adding some fruit to our tree

Adding nodes to our tree

Exploring the tree

Adding other Fruits

Share this:

Like this:

Related

You may also like...

Amazing Learning

Crates and cargo

Python REPL