Traversing in Data Structure: Binary Tree vs Binary Search Tree

For the most part, it’s possible you’ve dealt with arrays when writing Rust programs. In Rust, an array uses a linear data structure that collects data of similar data types, storing them in adjacent memory locations. Since the array utilizes a linear structure, the data is connected in such a way that the data is immediately connected to its prior and the subsequent data. This means that we can traverse all the data elements in a run. Therefore, when we’re dealing with large data, it’ll take a lot of time to manage data in an array.

For this reason, developers utilize a non-linear data structure when dealing with a lot of data. This is because for non-linear data structures like trees, we can’t traverse all nodes in a Binary search tree at a run. This reduces the time complexity for managing large data, when compared with linear structures like arrays.

In this article, we’ll explore Binary Tree and Binary Search Tree in Rust. First, let’s see a brief introduction of data management in arrays and trees.

Data Traversal in Linear vs Non-Linear Data Structure, Exploring Arrays and Binary Tree

In our opening paragraph, we looked at traversing all elements in an array, when looking for a component.

From the image above, since we’re trying to retrieve the number with the 5th index (№6), which is towards the end of the array, we have to loop through our array. For the example above, it won’t be much of a problem managing data from an array of that size. However, how do we manage large data with an array? This means we’ll have to traverse through all elements in a large, in search of the element of interest.

On the other hand, non-linear data structures like Binary trees, store data in such a way that you don’t have to traverse through all nodes in the tree at a time, to retrieve the data of interest.

From the image above, if we’re trying to retrieve data from the tree structure, we’ll first traverse through the root, next, the left subtree, then to the right subtree. This means the time complexity won’t increase with an increase in data, since we’re taking one subtree at a time.

What is a Binary Tree

A Binary tree is a non-linear tree structure. A tree data structure, utilizes a hierarchical structure format. Here, data isn’t stored adjacent to each other like in an array. Instead, data are linked to each other in parent-child relationships, like a family tree. Each node in a binary tree contains at most two children, which are referred to as the left and right child, or subtree.

While we’ve seen that a Binary tree can be very useful when dealing with large data, that’s not the only use of a binary tree. For instance, binary trees can be used to emulate a decision tree algorithm.

They’re different types of binary tree. However, for the sake of this article we won’t dive into that. Instead, we’ll explore traversing in a Binary and Binary Search Tree.

What is a Binary Search Tree

A Binary Search tree is also known as a sorted binary tree. It is a sorted binary tree, because it contains a maximum of two children in each node, just like a Binary tree. However, a Binary Search Tree is ordered. For instance, a BST follows this order:

• Element in the right node is larger than the subtree root.
• Element in the left node is lesser than the subtree root.
• The above also applies to the root node.

The feature above, makes it easier to search for the element of interest. For example, we can determine which node to traverse, by looking at the element in consecutive root nodes. If the numbers in the left root node are way smaller than the number of interest, we don’t have to traverse through its left and right children. Next, we move to the right root node.

Creating a Binary Tree in Rust

The first thing we’ll be creating is the struct for our Binary tree. Recall that our Binary tree can have at most 2 children. This means, it can also have one or no children at all. To express this, we’ll be using Rust’s Option<>. Since the left and right nodes will likely contain a left and right node of their own, the type for the left and right node will be the BinaryTree. This makes it a recursive type, which has an infinite size. However, in Rust all values are allocated in the stack by default, the compiler needs to know the size of each value. To move past this hurdle, we’ll use a smart pointer, like Box, to put our type on the heap instead of the stack. We also want a value field for the data of the node.

Next, we’ll write functions for creating a root node.

Next, we’ll add functions for the left and right nodes into our impl.

We can test out our implementation, by creating a Binary tree, with the specifications below:

One way we can search for an element in this Binary tree, is to implement breadth-first search.

Creating a Binary Search Tree in Rust

The Binary search tree will follow the same process as our Binary tree. However, we’ll order its value so that the higher value goes to the right while the lesser value goes to the left. We’ll also have different structs for our BST root, since we want to keep track of the root. Then, another struct will hold our Node, with the left and right subtrees. Our struct for the binary search tree and node will look like this:

Next, we’ll write our implementation for the new and insert function.

We’ll be recursively searching through every node, until the value is inserted. However, since we’ll be comparing values, we have to implement the PartialOrd for T.

We now have a working BST that we can test with the specifications below:

Testing this is the same process as our BT. However, instead of looping through each node to find the number of interest, we can compare root nodes, to determine which node could possibly contain the data of interest.

Conclusion

In this article, we’ve explored binary trees and binary search trees. We’ve also discussed traversing in the binary and binary search tree structures.

Since I so badly wanted to complete this task that Akin has given me, I made a lot of compromise. First, in order to deal with the stack overflow error from calling a recursive function (push_node), I made some last minute changes, using this guide. This is still a work in progress and I’ll be fixing all the compromises I made, when I get the chance.

Feel free to leave a comment or contact me via Twitter, if you have any questions or suggestions.