A leaf node in a binary tree refers to a node that has no child nodes. Write a function to count the number of leaf nodes in a given binary tree.<\/p>\n
For example:<\/p>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n <\/pre>\n<\/li>\n
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.<\/p>\n
To find the leaf nodes, the following steps are followed:<\/p>\n
Now, let’s implement the above algorithm in Swift. Below is the code for the function that counts the number of leaf nodes:<\/p>\n
\n class TreeNode {\n var value: Int\n var left: TreeNode?\n var right: TreeNode?\n \n init(value: Int) {\n self.value = value\n self.left = nil\n self.right = nil\n }\n }\n\n func countLeafNodes(root: TreeNode?) -> Int {\n guard let node = root else {\n return 0\n }\n \n \/\/ Check if it is a leaf node\n if node.left == nil && node.right == nil {\n return 1\n }\n \n \/\/ Recursively count the number of leaf nodes in the left and right child nodes\n return countLeafNodes(root: node.left) + countLeafNodes(root: node.right)\n }\n <\/pre>\nCode Explanation<\/h2>\n
The above code implements the countLeafNodes<\/code> function to count the number of leaf nodes in a binary tree. I will describe each part:<\/p>\n\nTreeNode<\/code> class: Defines each node in the binary tree. Each node has a value and left and right children.<\/li>\ncountLeafNodes<\/code> function: Takes a given node as an argument and returns the number of leaf nodes.<\/li>\nguard let<\/code>: Checks if the current node is NULL, and if it is, returns 0 to terminate the search.<\/li>\n- Leaf node check: Returns 1 if the current node has no left and right child nodes.<\/li>\n
- Recursive calls: Recursively calls the left and right child nodes and adds up the number of leaf nodes.<\/li>\n<\/ul>\n
Test Cases<\/h2>\n
Let’s create some test cases to verify that the function works correctly.<\/p>\n
\n \/\/ Create tree\n let root = TreeNode(value: 1)\n let node2 = TreeNode(value: 2)\n let node3 = TreeNode(value: 3)\n let node4 = TreeNode(value: 4)\n let node5 = TreeNode(value: 5)\n\n \/\/ Connect tree structure\n root.left = node2\n root.right = node3\n node2.left = node4\n node2.right = node5\n\n \/\/ Output the number of leaf nodes\n let leafCount = countLeafNodes(root: root)\n print(\"Number of leaf nodes: \\(leafCount)\") \/\/ Number of leaf nodes: 3\n <\/pre>\nConclusion<\/h2>\n
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.<\/p>\n
Additional Learning Resources<\/h2>\n
If you want to find more resources related to the problem of counting leaf nodes, consider the following materials:<\/p>\n