Python Coding Test Course, Counting the Number of Leaf Nodes

Problem Description

Write a function to traverse the given binary tree and calculate the number of leaf nodes. A leaf node is defined as a node that has no child nodes.

Input

• A node object representing the root of the tree, given as a Node class.

Output

• An integer value representing the number of leaf nodes.

Constraints

• The tree can have a maximum of 10⁴ nodes.

Creating and Structuring a Binary Tree

A binary tree is a data structure where each node can have at most two child nodes. Essentially, a binary tree starts from the root node and is composed of child nodes. Below is a way to define the node class for a binary tree.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

In the code above, the Node class stores the value of each node and includes pointers that reference the left and right child nodes. Now, we can use this node structure to create a binary tree.

Counting Leaf Nodes

A leaf node is a node that has no child nodes, and to count them, we need to traverse the tree. Generally, there are three methods to traverse a binary tree: preorder, inorder, and postorder. Here, we will look at how to count leaf nodes using postorder traversal.

Postorder Traversal Algorithm

Postorder traversal is conducted through the following steps:

1. Traverse the left subtree in postorder.
2. Traverse the right subtree in postorder.
3. Visit the current node.

Using this process, we can verify whether a parent node is a leaf node. If it is a leaf node, we increase the counter to count the number of leaf nodes.

Code Implementation

def count_leaf_nodes(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

The above count_leaf_nodes function recursively traverses the binary tree to calculate the number of leaf nodes.

Detailed Explanation of the Problem-Solving Process

Let’s take a step-by-step look at how to solve this problem.

Step 1: Basic Tree Creation

To create a binary tree, we need to define a few nodes. For example, let us consider a tree like the following.

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

The code above constructs the following binary tree:

Step 2: Testing the Basic Function

Now, we can use the count_leaf_nodes function we implemented to calculate the number of leaf nodes.

leaf_count = count_leaf_nodes(root)
print(f"Number of leaf nodes: {leaf_count}")

Executing the above code will output the number of leaf nodes in the binary tree. In this case, there are 3 leaf nodes (4, 5, 6), so the output will be “Number of leaf nodes: 3”.

Time Complexity Analysis

The time complexity of the above algorithm is O(n), since it visits all nodes present in the tree. n represents the number of nodes.

Conclusion

In today’s lecture, we addressed the problem of counting leaf nodes in a binary tree. In this process, we applied recursive approaches and the concept of postorder traversal. This problem frequently appears not only in coding tests but also in practical development, so be sure to understand it thoroughly.

In the next lecture, we will explore binary trees in greater depth and cover various tree problems. Thank you.