Hello! In this post, we will solve an algorithm problem based on the theme “Command of Jumong” for those preparing for coding tests with JavaScript. Throughout this process, we’ll thoroughly explain how to understand the problem, the approach, code implementation, and time complexity analysis.<\/p>\n
Despite the winter, Jumong issued commands to his subordinates. His commands are given in the following format:<\/p>\n
In this problem, we must clearly understand what a path in the tree is and how to traverse it. A path refers to the set of all nodes moving from the root to a leaf node.<\/p>\n
\n{\n \"root\": {\n \"value\": 1,\n \"left\": {\n \"value\": 2,\n \"left\": null,\n \"right\": {\n \"value\": 3,\n \"left\": null,\n \"right\": null\n }\n },\n \"right\": {\n \"value\": 4,\n \"left\": null,\n \"right\": null\n }\n },\n \"x\": 1\n}\n<\/pre>\nOutput Format<\/h2>\n
Return the sum of the occurrences of x in all paths containing the number x in the given binary tree.<\/p>\n
\n{\n \"result\": 2\n}\n<\/pre>\nApproach to the Problem<\/h2>\n
To solve this problem, we will use the DFS (Depth-First Search) algorithm. It involves counting `x` while traversing the binary tree in a depth-first manner along the paths.<\/p>\n
Step 1: Tree Traversal<\/h3>\n
First, we write a recursive function that can traverse the tree. This function takes the current node, the count of x included in the current path, and a variable to store the result as arguments.<\/p>\n
Step 2: Save Path and Check Conditions<\/h3>\n
We check if the node is a leaf node, and when we reach a leaf node, we add the count of x included in the path to the result variable. If the current node is not a leaf, we recursively traverse the left and right child nodes.<\/p>\n
Step 3: Time Complexity Analysis<\/h3>\n
The time complexity of this algorithm is O(n) since we visit each node in the tree once.<\/p>\n
Code Implementation<\/h2>\n\nfunction countXPaths(root, x) {\n let totalPathsCount = 0;\n\n function dfs(node, currentCount) {\n if (node === null) {\n return;\n }\n\n \/\/ Check the value of the current node\n let newCount = currentCount + (node.value === x ? 1 : 0);\n\n \/\/ Check if it's a leaf node\n if (node.left === null && node.right === null) {\n totalPathsCount += newCount;\n return;\n }\n\n \/\/ Traverse the left and right child nodes\n dfs(node.left, newCount);\n dfs(node.right, newCount);\n }\n\n dfs(root, 0);\n return { result: totalPathsCount };\n}\n<\/code><\/pre>\nTest Cases<\/h2>\n
Now, let’s create various test cases to ensure that the code we wrote works as expected.<\/p>\n
\n\/\/ Test Case 1\nconst testCase1 = {\n root: {\n value: 1,\n left: {\n value: 2,\n left: null,\n right: {\n value: 1,\n left: null,\n right: null\n }\n },\n right: {\n value: 4,\n left: null,\n right: null\n }\n },\n x: 1\n};\nconsole.log(countXPaths(testCase1.root, testCase1.x)); \/\/ Output: { result: 2 }\n\n\/\/ Test Case 2\nconst testCase2 = {\n root: {\n value: 2,\n left: {\n value: 1,\n left: null,\n right: null\n },\n right: {\n value: 1,\n left: {\n value: 3,\n left: null,\n right: null\n },\n right: null\n }\n },\n x: 1\n};\nconsole.log(countXPaths(testCase2.root, testCase2.x)); \/\/ Output: { result: 3 }\n\n\/\/ Test Case 3\nconst testCase3 = {\n root: {\n value: 5,\n left: {\n value: 1,\n left: {\n value: 1,\n left: null,\n right: null\n },\n right: {\n value: 2,\n left: null,\n right: null\n }\n },\n right: {\n value: 7,\n left: null,\n right: null\n }\n },\n x: 1\n};\nconsole.log(countXPaths(testCase3.root, testCase3.x)); \/\/ Output: { result: 2 }\n<\/code><\/pre>\nConclusion<\/h2>\n
In this post, we understood and implemented the concepts of depth-first search and recursive functions through the algorithm problem called “Command of Jumong.” By creating various test cases, we increased the reliability of the code and systematically organized how to solve the problem step by step.<\/p>\n
The mindset for approaching problems and implementation skills are very important in the process of preparing for coding tests. Continuously practicing will help you become familiar with solving such problems.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"