Constructing a Tree of Minimal Height.

In this small story we are going to look at the construction of a tree with minimal height from a list of values. To understand all the content you should have some basic understanding of Rust. You may obtain in from here if necessary.

Problem:

We are given a list of positive integers and are requested to construct a binary tree that is minimum in height and associates each nodes with exactly one value in that list.

Solution:

Beside there are several solution to this problem, one very easy is described as follows:

1. Create a root node and associate the first value in the list with it.
2. For each element of the list as long as the maximal level of the tree still is not fully occupied, do create child nodes in this level and associate the values accordingly.
3. If the maximal level is fully occupied, do proceed by creating nodes in one level further and make this the new maximal level.

In other words, we are going to fill up the tree level-by-level and ensure at the same time the tree to be a binary tree.

Although it is standard notation, let me mention that a level of height x is defined to be the set of nodes that are reachable from the root node by a path containing exactly x nodes.

Implementation:

The tree will be represented by the following struct:

#[derive(Default)] 
pub struct Node {
    pub value: u32,
    pub left: Option<Rc<RefCell<Node>>>,
    pub right: Option<Rc<RefCell<Node>>>,
}

The reason why we implement the trait Default will be explained soon. As you see, the tree’s child nodes are optional made Rc references wrapping RefCell. We use Rc in order to allow a node being referenced from different variables independent of any life time. RefCell is a standard way of obtaining a mutable reference through such an actual read-only Rc reference.

Also, we implement the following utility functions on Nodes:

impl Node {
    pub fn new(value: u32) -> Node {
        Node {
            value,
            left: None,
            right: None,
        }
    }