C# Coding Test Course, Counting the Number of Leaf Nodes

Hello, everyone! Today we will learn how to solve algorithm problems using C#. The topic for this session is to find the number of leaf nodes in a binary tree. By solving this problem, you can enhance your understanding of data structures and recursive calls.

1. Problem Definition

The problem is as follows: Given a binary tree, write a function to count the number of leaf nodes (nodes with no children).

Example

Input: A binary tree as follows

Output: 3 (Leaf nodes: 4, 5, 3)

2. Introduction to Binary Trees

A binary tree is a tree data structure in which each node can have at most two children. A binary tree has the following characteristics:

Each node can have child nodes (left and right).
A leaf node refers to a node that has no child nodes.
A binary tree has a recursive structure.

3. Approach

To count the number of leaf nodes, let’s consider using a recursive function. The basic approach is as follows:

Examine the current node. If the current node is null, return 0.
If the current node is a leaf node (i.e., both left and right children are null), return 1.
If the current node is not a leaf node, recursively count the number of leaf nodes in the left and right subtrees and return the sum.

4. C# Code Implementation

Now, let’s implement the code in C# according to the approach described above.

using System;

class TreeNode
{
    public int Val;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int val)
    {
        Val = val;
        Left = null;
        Right = null;
    }
}

class Program
{
    public static int CountLeafNodes(TreeNode root)
    {
        // 1. If the current node is null
        if (root == null)
            return 0;

        // 2. If the current node is a leaf node
        if (root.Left == null && root.Right == null)
            return 1;

        // 3. Count leaf nodes in the left and right subtrees
        return CountLeafNodes(root.Left) + CountLeafNodes(root.Right);
    }

    static void Main(string[] args)
    {
        // Create the tree
        TreeNode root = new TreeNode(1);
        root.Left = new TreeNode(2);
        root.Right = new TreeNode(3);
        root.Left.Left = new TreeNode(4);
        root.Left.Right = new TreeNode(5);

        // Print the count of leaf nodes
        int leafCount = CountLeafNodes(root);
        Console.WriteLine($"Number of leaf nodes: {leafCount}");
    }
}

5. Code Explanation

The provided TreeNode class defines a node in the binary tree. Each node has a value (Val) and left (Left) and right (Right) child nodes. The CountLeafNodes function recursively calculates the number of leaf nodes for the given node.

In the first conditional statement, if the current node is null, it returns 0 to terminate.
In the second conditional statement, if the current node is a leaf node, it returns 1.
Finally, it visits the left and right subtrees, sums up the results, and returns the total.

6. Time Complexity Analysis

The time complexity of this algorithm is O(N). Here, N represents the number of nodes in the tree. Since each node is visited only once, it has a linear time complexity.

7. Additional Considerations

If the tree is empty, i.e., the root node is null, there are no leaf nodes.
Both balanced binary trees and skewed binary trees can handle the problem in the same way.

8. Conclusion

We learned how to solve the problem of counting leaf nodes in a binary tree. We can easily resolve this using a recursive function, thereby enhancing our understanding of tree data structures.

Next time, we will tackle another algorithm problem and advance further. Thank you!