Swift Coding Test Course, Counting Leaf Nodes

Problem Description

Problem Analysis

This problem involves implementing an algorithm that can count the number of nodes with no child nodes (i.e., leaf nodes) in the given binary tree. You can traverse the binary tree using either a recursive or iterative approach to find the leaf nodes.

Algorithm Design

To find the leaf nodes, the following steps are followed:

1. Define a function to traverse the binary tree.
2. If the current node is not NULL:
• Recursively call the left child node.
• Recursively call the right child node.
• Check if the current node is a leaf node; if it is, increment the count.
3. If it is NULL, the function terminates.

Swift Implementation

Now, let’s implement the above algorithm in Swift. Below is the code for the function that counts the number of leaf nodes:

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
            self.left = nil
            self.right = nil
        }
    }

    func countLeafNodes(root: TreeNode?) -> Int {
        guard let node = root else {
            return 0
        }
        
        // Check if it is a leaf node
        if node.left == nil && node.right == nil {
            return 1
        }
        
        // Recursively count the number of leaf nodes in the left and right child nodes
        return countLeafNodes(root: node.left) + countLeafNodes(root: node.right)
    }
    

Code Explanation

The above code implements the countLeafNodes function to count the number of leaf nodes in a binary tree. I will describe each part:

• TreeNode class: Defines each node in the binary tree. Each node has a value and left and right children.
• countLeafNodes function: Takes a given node as an argument and returns the number of leaf nodes.
• guard let: Checks if the current node is NULL, and if it is, returns 0 to terminate the search.
• Leaf node check: Returns 1 if the current node has no left and right child nodes.
• Recursive calls: Recursively calls the left and right child nodes and adds up the number of leaf nodes.

Test Cases

Let’s create some test cases to verify that the function works correctly.

    // Create tree
    let root = TreeNode(value: 1)
    let node2 = TreeNode(value: 2)
    let node3 = TreeNode(value: 3)
    let node4 = TreeNode(value: 4)
    let node5 = TreeNode(value: 5)

    // Connect tree structure
    root.left = node2
    root.right = node3
    node2.left = node4
    node2.right = node5

    // Output the number of leaf nodes
    let leafCount = countLeafNodes(root: root)
    print("Number of leaf nodes: \(leafCount)")  // Number of leaf nodes: 3
    

Conclusion

In this article, we explored how to count the number of leaf nodes in a binary tree using Swift. In the process of designing the algorithm and implementing it, we understood the principles of recursive calls and practiced writing actual code. Such problems are frequently encountered in coding tests, so it’s important to practice repeatedly to enhance your proficiency.

Additional Learning Resources

If you want to find more resources related to the problem of counting leaf nodes, consider the following materials:

• GeeksforGeeks: Count Leaf Nodes in Binary Tree
• LeetCode: Number of Leaf Nodes in Binary Tree
• HackerRank: Tree Level Order Traversal