Kotlin Coding Test Course, Counting the Number of Leaf Nodes

Hello, everyone! In this course, we will address an algorithm problem to count the number of leaf nodes using Kotlin. Leaf nodes refer to nodes without any children in a binary tree, and we will explore efficient ways to process this data.

Problem Description

Given a binary tree, write a function to count the number of leaf nodes. Leaf nodes are defined as nodes without children. We will use the class structure below to solve this problem:

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

Input Example

  • Tree Structure
    •         1
       / \
      2   3
     / \
    4   5

Output Example

  • Number of Leaf Nodes: 3

Approach to Problem Solving

To solve this problem, we will use a recursive method. We will traverse the tree and check whether each node is a leaf node, counting it if it is. The specific steps are as follows:

  1. As a base case, return 0 if the current node is null.
  2. If the current node is a leaf node (i.e., both left and right children are null), return 1.
  3. If not, recursively traverse the left and right subtrees and add up the counts of leaf nodes.

Code Implementation

Let’s implement the code based on the above approach:

fun countLeafNodes(root: TreeNode?): Int {
    // Base case: current node is null
    if (root == null) {
        return 0
    }
    
    // If it's a leaf node
    if (root.left == null && root.right == null) {
        return 1
    }
    
    // Recursively calculate the number of leaf nodes in the left and right subtrees
    return countLeafNodes(root.left) + countLeafNodes(root.right)
}

Test Cases

Let’s write several test cases to ensure the function works correctly:

fun main() {
    // Example tree creation
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    
    // Count the number of leaf nodes
    val leafCount = countLeafNodes(root)
    println("Number of leaf nodes: $leafCount") // Expected output: 3
}

Complexity Analysis

The time complexity of this problem is O(n), as we visit every node once. The space complexity is O(h), where h is the height of the tree, determined by the function call stack.

Conclusion

In this course, we solved the problem of counting leaf nodes in a binary tree using Kotlin. We were able to enhance our understanding of recursion and data structures during the algorithm problem-solving process. I hope to learn more through additional problems!

Thank you. See you in the next course!