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 treelet 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 nodeslet 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.