Rust Program to Count number of leaf nodes in a tree

Count number of leaf nodes in a tree

Rust Programming Language

Problem

Rust program that counts the number of leaf nodes in a 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 is_leaf(&self) -> bool {
self.left.is_none() && self.right.is_none()
}
}

fn count_leaf_nodes(root: Option<Box<TreeNode>>) -> i32 {
match root {
Some(node) => {
if node.is_leaf() {
1
} else {
count_leaf_nodes(node.left) + count_leaf_nodes(node.right)
}
}
None => 0,
}
}

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)));

// Count the number of leaf nodes
let num_leaves = count_leaf_nodes(Some(Box::new(root)));
println!("The tree has {} leaf nodes", num_leaves);
}{codeBox}

Output

The tree has 4 leaf nodes{codeBox}

Explanation

In this implementation, the TreeNode struct represents a node in the tree. Each node has a value and pointers to its left and right children. The is_leaf method checks whether a node is a leaf by testing whether its left and right children are both None. The count_leaf_nodes function recursively counts the number of leaf nodes in the tree by checking whether the root node is a leaf, and if not, recursively counting the number of leaf nodes in its left and right subtrees. The main function constructs a sample tree and prints out the number of leaf nodes in the tree.

the tree has four leaf nodes (the nodes with values 4, 5, 6, and 7). This program can be easily modified to suit different tree structures or algorithms.