Rust Program to Count number of leaf nodes in a tree

Count number of leaf nodes in a tree

Rust Programming Language

Count number of leaf nodes in a tree


Rust program that counts the number of leaf nodes in a tree.


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() {
            } 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);


The tree has 4 leaf nodes{codeBox}


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.

Post a Comment