Rust Program to Perform the preorder tree traversal

The preorder tree traversal

Rust Programming Language

Problem

Rust program that performs a preorder traversal of a binary tree.

Input

struct TreeNode {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}

impl TreeNode {
fn new(val: i32) -> Self {
Self { val, left: None, right: None }
}
}

fn preorder_traversal(root: Option<Box<TreeNode>>) {
if let Some(node) = root {
println!("{}", node.val);
preorder_traversal(node.left);
preorder_traversal(node.right);
}
}

fn main() {
// Construct the tree
let mut root = TreeNode::new(1);
root.left = Some(Box::new(TreeNode::new(2)));
root.right = Some(Box::new(TreeNode::new(3)));
root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));
root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));
root.right.as_mut().unwrap().left = Some(Box::new(TreeNode::new(6)));
root.right.as_mut().unwrap().right = Some(Box::new(TreeNode::new(7)));

// Perform the preorder traversal
println!("Preorder traversal:");
preorder_traversal(Some(Box::new(root)));
}{codeBox}

Output

Preorder traversal:
1
2
4
5
3
6
7{codeBox}

Explanation

In this implementation, the TreeNode struct represents a node in the binary tree. Each node has a value and pointers to its left and right children. The preorder_traversal function performs a preorder traversal of the tree recursively by first printing the current node's value, then visiting the left subtree, and finally visiting the right subtree. The main function constructs a sample tree and performs a preorder traversal of the tree, printing out the values of each visited node.

The preorder traversal visits the nodes of the tree in a "top-down" order, where the current node is visited before its children. This program can be easily modified to suit different tree structures or algorithms.