Hello, everyone! Today, we will explore binary trees and take some time to solve related problems. A binary tree is one of the fundamental structures in computer science and algorithms, and it is a topic that frequently appears in job coding tests. In this article, we will introduce the basic concepts of binary trees, present a problem using these concepts, and explain the process of solving the problem with Kotlin in detail.<\/p>\n
A binary tree is a tree structure where each node can have at most two children. Each node contains data and references to its child nodes. Binary trees are used for various purposes and play a significant role in tree traversal, sorting algorithms, and more.<\/p>\n
\nclass TreeNode(val value: Int) {\n var left: TreeNode? = null\n var right: TreeNode? = null\n}\n<\/pre>\nIn the code above, the TreeNode<\/code> class represents each node in a binary tree. The value<\/code> is the value of the node, and left<\/code> and right<\/code> represent the left and right children, respectively.<\/p>\nProblem Statement<\/h2>\n
Now, I will present the problem we will solve. It is a problem of counting the number of paths in a given binary tree where the sum of nodes along each path equals a specified value.<\/p>\n
Problem Description<\/h3>\n
Write a function to calculate the sum of paths from the root node of a given binary tree to each leaf node, and print the number of paths where this sum equals a given value.<\/p>\n
Input:<\/strong><\/p>\n\n- The
root<\/code> representing the root node of the binary tree.<\/li>\n- An integer
sum<\/code>, the sum of the path you want to find.<\/li>\n<\/ul>\nOutput:<\/strong><\/p>\n\n- The number of paths that match the given
sum<\/code>.<\/li>\n<\/ul>\nExample<\/h3>\n\nInput:\n 5\n \/ \\\n 4 8\n \/ \/ \\\n 11 13 4\n \/ \\ \\\n 7 2 1\nsum = 22\n\nOutput:\n3\n<\/pre>\nProblem-Solving Process<\/h2>\n
To solve this problem, we will use the DFS (Depth-First Search) algorithm. DFS is a useful method for traversing trees, visiting nodes through recursive calls.<\/p>\n
Problem-Solving Approach<\/h3>\n\n- Explore each path using DFS.<\/li>\n
- Keep an accumulated sum as you visit each node.<\/li>\n
- When you reach a leaf node, check if the accumulated sum equals
sum<\/code>.<\/li>\n- If they are equal, increase the count.<\/li>\n<\/ol>\n
Kotlin Code<\/h3>\n\nfun pathSum(root: TreeNode?, sum: Int): Int {\n return findPaths(root, sum, 0)\n}\n\nfun findPaths(node: TreeNode?, target: Int, currentSum: Int): Int {\n if (node == null) {\n return 0\n }\n\n val newSum = currentSum + node.value\n var pathCount = 0\n\n if (node.left == null && node.right == null && newSum == target) {\n pathCount += 1\n }\n\n pathCount += findPaths(node.left, target, newSum)\n pathCount += findPaths(node.right, target, newSum)\n\n return pathCount\n}\n<\/pre>\nCode Explanation<\/h2>\n
The code above is a function that calculates the sum of paths in a given binary tree. The pathSum<\/code> function takes the provided root<\/code> and sum<\/code> as input and returns the number of paths. The findPaths<\/code> function recursively explores nodes and calculates the sum of paths. When reaching each leaf node, it checks if the accumulated sum is equal to target<\/code>, and if it is, it increases the path count.<\/p>\nTest Cases<\/h2>\n
Now let’s test the function we have written. By applying various test cases, we will validate the algorithm’s accuracy.<\/p>\n
\nfun main() {\n \/\/ Sample test case\n val root = TreeNode(5).apply {\n left = TreeNode(4).apply {\n left = TreeNode(11).apply {\n left = TreeNode(7)\n right = TreeNode(2)\n }\n }\n right = TreeNode(8).apply {\n left = TreeNode(13)\n right = TreeNode(4).apply {\n right = TreeNode(1)\n }\n }\n }\n \n val sum = 22\n val result = pathSum(root, sum)\n println(\"Number of paths: $result\") \/\/ Output: Number of paths: 3\n}\n<\/pre>\nConclusion<\/h2>\n
In this article, we solved an algorithm problem using binary trees. We learned how to calculate the sum of each path using DFS and explored specific code writing methods in Kotlin. Since binary trees are widely used as a fundamental data structure to solve various problems, it is beneficial to apply them to multiple problem scenarios.<\/p>\n
That concludes this tutorial. Let’s continue to improve our skills by solving more algorithm problems together!<\/p>\n","protected":false},"excerpt":{"rendered":"