Rust Program to Perform the postorder tree traversal

The postorder tree traversal

Rust Programming Language

Problem

Rust program that performs a postorder 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 postorder_traversal(root: Option<Box<TreeNode>>) {
if let Some(node) = root {
postorder_traversal(node.left);
postorder_traversal(node.right);
println!("{}", node.val);
}
}

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 postorder traversal
println!("Postorder traversal:");
postorder_traversal(Some(Box::new(root)));
}{codeBox}

Output

Postorder traversal:
4
5
2
6
7
3
1{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 postorder_traversal function performs a postorder traversal of the tree recursively by first visiting the left subtree, then visiting the right subtree, and finally printing the current node's value. The main function constructs a sample tree and performs a postorder traversal of the tree, printing out the values of each visited node.