JavaScript Coding Test Course, Jumong's Command

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.

Problem Description

Despite the winter, Jumong issued commands to his subordinates. His commands are given in the following format:

A binary tree is given.
Each node contains an integer from 0 to n.
When a number x commanded by Jumong is provided, we need to count the occurrences of x in all paths of the binary tree.

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.

Input Format

{
    "root": {
        "value": 1,
        "left": {
            "value": 2,
            "left": null,
            "right": {
                "value": 3,
                "left": null,
                "right": null
            }
        },
        "right": {
            "value": 4,
            "left": null,
            "right": null
        }
    },
    "x": 1
}

Output Format

Return the sum of the occurrences of x in all paths containing the number x in the given binary tree.

{
    "result": 2
}

Approach to the Problem

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.

Step 1: Tree Traversal

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.

Step 2: Save Path and Check Conditions

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.

Step 3: Time Complexity Analysis

The time complexity of this algorithm is O(n) since we visit each node in the tree once.

Code Implementation


function countXPaths(root, x) {
    let totalPathsCount = 0;

    function dfs(node, currentCount) {
        if (node === null) {
            return;
        }

        // Check the value of the current node
        let newCount = currentCount + (node.value === x ? 1 : 0);

        // Check if it's a leaf node
        if (node.left === null && node.right === null) {
            totalPathsCount += newCount;
            return;
        }

        // Traverse the left and right child nodes
        dfs(node.left, newCount);
        dfs(node.right, newCount);
    }

    dfs(root, 0);
    return { result: totalPathsCount };
}

Test Cases

Now, let’s create various test cases to ensure that the code we wrote works as expected.


// Test Case 1
const testCase1 = {
    root: {
        value: 1,
        left: {
            value: 2,
            left: null,
            right: {
                value: 1,
                left: null,
                right: null
            }
        },
        right: {
            value: 4,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase1.root, testCase1.x)); // Output: { result: 2 }

// Test Case 2
const testCase2 = {
    root: {
        value: 2,
        left: {
            value: 1,
            left: null,
            right: null
        },
        right: {
            value: 1,
            left: {
                value: 3,
                left: null,
                right: null
            },
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase2.root, testCase2.x)); // Output: { result: 3 }

// Test Case 3
const testCase3 = {
    root: {
        value: 5,
        left: {
            value: 1,
            left: {
                value: 1,
                left: null,
                right: null
            },
            right: {
                value: 2,
                left: null,
                right: null
            }
        },
        right: {
            value: 7,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase3.root, testCase3.x)); // Output: { result: 2 }

Conclusion

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.

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.

JavaScript Coding Test Course, Jumong’s Command