Rust Program to Perform the preorder tree traversal


The preorder tree traversal

Rust Programming Language


The preorder tree traversal


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.



Post a Comment