{"id":34994,"date":"2024-11-01T09:34:23","date_gmt":"2024-11-01T09:34:23","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34994"},"modified":"2024-11-01T11:45:25","modified_gmt":"2024-11-01T11:45:25","slug":"kotlin-coding-test-course-counting-the-number-of-leaf-nodes","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34994\/","title":{"rendered":"Kotlin Coding Test Course, Counting the Number of Leaf Nodes"},"content":{"rendered":"

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.<\/p>\n

Problem Description<\/h2>\n

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:<\/p>\n

\nclass TreeNode(val value: Int) {\n    var left: TreeNode? = null\n    var right: TreeNode? = null\n}\n<\/pre>\n
Input Example<\/h3>\n
    \n
  • Tree Structure<\/li>\n
    \n        1\n       \/ \\\n      2   3\n     \/ \\\n    4   5\n    <\/pre>\n<\/ul>\n
    Output Example<\/h3>\n
      \n
    • Number of Leaf Nodes: 3<\/li>\n<\/ul>\n
      Approach to Problem Solving<\/h2>\n
      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:<\/p>\n
        \n
      1. As a base case, return 0 if the current node is null<\/code>.<\/li>\n
      2. If the current node is a leaf node (i.e., both left and right children are null<\/code>), return 1.<\/li>\n
      3. If not, recursively traverse the left and right subtrees and add up the counts of leaf nodes.<\/li>\n<\/ol>\n
        Code Implementation<\/h2>\n
        Let’s implement the code based on the above approach:<\/p>\n
        fun countLeafNodes(root: TreeNode?): Int {\n    \/\/ Base case: current node is null\n    if (root == null) {\n        return 0\n    }\n    \n    \/\/ If it's a leaf node\n    if (root.left == null && root.right == null) {\n        return 1\n    }\n    \n    \/\/ Recursively calculate the number of leaf nodes in the left and right subtrees\n    return countLeafNodes(root.left) + countLeafNodes(root.right)\n}\n<\/code><\/pre>\n
        Test Cases<\/h2>\n
        Let’s write several test cases to ensure the function works correctly:<\/p>\n
        fun main() {\n    \/\/ Example tree creation\n    val root = TreeNode(1).apply {\n        left = TreeNode(2).apply {\n            left = TreeNode(4)\n            right = TreeNode(5)\n        }\n        right = TreeNode(3)\n    }\n    \n    \/\/ Count the number of leaf nodes\n    val leafCount = countLeafNodes(root)\n    println(\"Number of leaf nodes: $leafCount\") \/\/ Expected output: 3\n}\n<\/code><\/pre>\n
        Complexity Analysis<\/h2>\n
        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.<\/p>\n
        Conclusion<\/h2>\n
        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!<\/p>\n
        Thank you. See you in the next course!<\/p>\n

        \n<\/p>\n