Category: C++ Coding Test Tutorials

A binary tree is one of the important data structures in computer science,
where each node has at most two child nodes.
Binary trees are used for various purposes such as searching, sorting, and data storage,
and frequently appear in algorithm problems.
In this lecture, we will solve algorithm problems utilizing binary trees.

Problem: Finding the Maximum Depth of a Binary Tree

The problem is to traverse a given binary tree and calculate its depth.
The maximum depth refers to the length of the path from the root node to the deepest leaf node.
If the binary tree is empty, the depth is 0.
The following are the input and output formats.

Input Format

The binary tree is given in the form of an array, and each node is defined as follows:

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    

Output Format

Returns the maximum depth of the binary tree as an integer.

Example

    Input: [3,9,20,null,null,15,7]
    Output: 3
    

Problem Solving Approach

To solve this problem, a method to traverse the binary tree is required.
We can mainly traverse in two ways:
depth-first search (DFS) or breadth-first search (BFS).
In this case, we will choose to use DFS to recursively traverse the tree.

Depth-First Search – Recursive Method

Through recursion, we visit each node of the tree and
continuously call the left and right child nodes to check the depth.
Below is the core idea of the algorithm representing this process.

1. If the current node is NULL, return 0.
2. Recursively call the left subtree to obtain its depth.
3. Recursively call the right subtree to obtain its depth.
4. Select the greater of the left and right depths and add 1 before returning.

Implementation

Now, let’s implement the above-described algorithm in C++ code.

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (root == NULL) {
                return 0;
            }
            int leftDepth = maxDepth(root->left);
            int rightDepth = maxDepth(root->right);
            return max(leftDepth, rightDepth) + 1;
        }
    };
    

Code Explanation

The above code is a function written in C++ that calculates the maximum depth of a binary tree.
The maxDepth function is called recursively to calculate the
maximum depth of the given node.

• In if (root == NULL), we check if the node is NULL. If it is NULL, the depth is 0, so we return it.
• Calculate the depths for the left and right children and choose the larger value before adding 1.
• The final returned value is the overall maximum depth.

Testing

Now, let’s verify the functionality of the algorithm through some test cases.

    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    Solution solution;
    int result = solution.maxDepth(root);
    cout << result; // 3
    

Conclusion

We examined how to implement an algorithm that calculates the maximum depth of
a binary tree in C++.
Through this problem, we were able to learn the basics of recursive traversal,
which will serve as a foundation for solving more complex tree-related problems.
I hope you will continue to study binary trees in depth.
Thank you!

Binary Search is an efficient method for finding a specific value in a sorted array. This algorithm has a time complexity of O(log n) because it repeatedly divides the array in half to find the target value. In this lecture, we will cover the basic concepts of binary search, implementation methods, and practical exercises using this technique.

Basic Principle of Binary Search

Binary search operates according to the following procedure:

1. Check the central element of the array.
2. Compare the central element with the target value:
• If the target value is less than the central element, search in the left half of the array.
• If the target value is greater than the central element, search in the right half of the array.
• If the target value is equal to the central element, the search is complete.

This process is repeated until the target value is found.

Problem: Finding a Specific Value in a Sorted Array

Given an integer array arr and an integer target, write a program that returns the index of target. If target is not found, it should return -1.

Input Format

• The first line contains the size of the array n. (1 ≤ n ≤ 10⁵)
• The second line contains the sorted array arr in ascending order.
• The third line contains the number target to be found.

Output Format

Print the index of the target. (An integer between 0 and n-1)

Example

Input:
    5
    1 3 5 7 9
    5

    Output:
    2

Solution Process

Step 1: Understanding the Problem

First, it is important to accurately understand the problem. Since we need to quickly find a specific element in a sorted array, we should use binary search.

Step 2: Implementing the Binary Search Algorithm

Let’s implement the binary search algorithm in C++.

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;  // Found the target.
        } else if (arr[mid] < target) {
            left = mid + 1;  // Move to the right half.
        } else {
            right = mid - 1;  // Move to the left half.
        }
    }
    return -1;  // Target not found.
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    
    vector<int> arr(n);
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int target;
    cout << "Enter the number you want to find: ";
    cin >> target;

    int result = binarySearch(arr, target);
    if (result != -1) {
        cout << "Index of the target: " << result << endl;
    } else {
        cout << "Target not found." << endl;
    }

    return 0;
}

Step 3: Code Explanation

– The binarySearch function takes an integer vector and a target value as input and returns the index of the target value.
– left and right represent the start and end indices of the search interval.
– The while loop runs while left is less than or equal to right.
– In each iteration, the central index mid is computed, and the central element is compared with the target value to determine the next search interval.

Step 4: Testing and Verification

After writing the code, it is essential to run it against various test cases to ensure it returns the correct results. Consider the following tests:

• When the target value exists in the array
• When the target value does not exist in the array
• When the array size is 1
• When there are duplicate elements

Conclusion

Binary search is a very useful algorithm, especially as it exhibits excellent performance in terms of speed when working with sorted arrays. In this lecture, we understood the basic principles of binary search and implemented actual code. Mastering binary search will greatly help in solving many other algorithm problems.

In the next lecture, we will cover variations of binary search and various applications. I encourage you to enhance your algorithm skills through continuous learning!

Hello! Today we will learn about bipartite graphs. A bipartite graph is a graph in which the set of vertices can be divided into two subsets, and there are no edges between vertices within the same subset. This topic is one of the frequently posed questions in coding tests. In the next session, we will explore the algorithms and coding needed to determine if a graph is bipartite.

Problem Description

The problem is to determine whether the given undirected graph is bipartite. Starting from a vertex, we need to check whether we can visit all vertices while satisfying the bipartite graph conditions.

Problem Example

Given the following graph, determine whether it is a bipartite graph.

Vertices: 6
Edges: 
1 - 2
1 - 3
2 - 4
2 - 5
3 - 6

Looking at the graph above, we can see if it can be divided into two sets. Set A is {1, 4, 5, 6} and Set B is {2, 3}. This graph is indeed a bipartite graph.

Problem Solving Strategy

One method we can use to confirm if a graph is bipartite is Breadth-First Search (BFS) or Depth-First Search (DFS). Both methods can be employed to traverse the graph while coloring each vertex (or grouping them) to verify the bipartite graph conditions.

Algorithm Steps

1. Represent the graph in the form of an adjacency list.
2. Run a loop to visit all nodes.
3. Color the current vertex to divide it into two groups.
4. Check if adjacent vertices have the same color.
5. Repeat until all nodes have been visited or until all reachable nodes are visited.

C++ Code Implementation

Let’s take a look at the C++ code to determine if this undirected graph is bipartite.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 1000; // Maximum number of vertices
vector<int> graph[MAX];
int color[MAX]; // Color setting: -1 is unvisited, 0 and 1 are groups

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0; // Color the starting vertex

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int neighbor : graph[v]) {
            // If the neighboring vertex has not been visited, color it.
            if (color[neighbor] == -1) {
                color[neighbor] = 1 - color[v]; // Assign a different color than the current vertex
                q.push(neighbor);
            }
            // If the neighboring vertex has the same color as the current vertex, it is not a bipartite graph.
            else if (color[neighbor] == color[v]) {
                return false; // Violates the bipartite graph conditions
            }
        }
    }
    return true;
}

int main() {
    int v, e;
    cout << "Enter the number of vertices and edges: ";
    cin >> v >> e;

    // Initialize the graph
    for (int i = 0; i < MAX; i++) {
        color[i] = -1;
    }

    cout << "Input edges (format: a b): " << endl;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); // Undirected graph
    }

    bool result = true;
    for (int i = 1; i <= v; i++) {
        if (color[i] == -1) {
            // If this vertex is unvisited, check if it is bipartite
            if (!isBipartite(i)) {
                result = false;
                break;
            }
        }
    }

    if (result) {
        cout << "This graph is a bipartite graph." << endl;
    } else {
        cout << "This graph is not a bipartite graph." << endl;
    }

    return 0;
}

Code Explanation

This code takes the vertices and edges of the given graph as input and determines whether the graph is bipartite. The isBipartite function checks if all adjacent vertices are of different colors.

Variable and Structure Explanation

• graph[MAX]: Adjacency list representation of the graph.
• color[MAX]: An array representing the color of each vertex.
• queue<int> q: The queue used for BFS.

Input Example and Output Result

When running the code, an example of inputting edges is as follows.

Enter the number of vertices and edges: 6 5
Input edges (format: a b): 
1 2
1 3
2 4
2 5
3 6

When given the above input, the output will be as follows.

This graph is a bipartite graph.

Conclusion

In conclusion, we learned how to determine if a graph is bipartite using C++. Understanding the basic principle of solving problems using BFS or DFS can be applied to various graph problems. I hope this helps your preparation for coding tests!

Hello! In this article, we will learn about topological sorting. Topological sorting is an algorithm for linearly arranging the vertices in a directed acyclic graph (DAG), which is useful when a specific order needs to be maintained. For example, it is used when handling task dependencies or for compilers to determine the execution order of code.

Problem Description

Let’s solve the following problem.

Input

The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ 10000).

The next M lines contain pairs of x y, which means that task x must be performed before task y.

Output

Print the order in which the tasks can be performed, separated by spaces in a single line. If the order is not possible, print -1.

Example Input

    6 6
    1 2
    1 3
    2 4
    3 4
    4 5
    5 6
    

Example Output

1 2 3 4 5 6

Principle of Topological Sorting

Topological sorting can be implemented using two methods: DFS (Depth First Search) and BFS (Breadth First Search). Here, we will introduce Kahn’s algorithm using BFS. Kahn’s algorithm proceeds as follows.

1. Record the in-degree of all vertices.
2. Add the vertices with in-degree 0 to a queue.
3. Remove one vertex from the queue at a time and add it to the result list.
4. Remove all the edges going out from the removed vertex and update the in-degree of each destination vertex. Add any vertices that have an in-degree of 0 to the queue.
5. Repeat until the queue is empty. If the size of the result list is not equal to the number of input vertices, it means a cycle exists, so return -1.

Basic Code Implementation

Below is a basic implementation of topological sorting in C++.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSort(int n, vector<vector<int>> &graph) {
    vector<int> inDegree(n + 1, 0);
    vector<int> result;

    // Calculate in-degree
    for (int i = 1; i <= n; i++) {
        for (int j : graph[i]) {
            inDegree[j]++;
        }
    }

    queue<int> q;

    // Insert vertices with in-degree 0 into the queue
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // Check for cycles
    if (result.size() != n) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << ' ';
        }
        cout << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    topologicalSort(n, graph);
    return 0;
}
    

Code Explanation

In the above code, we first declare an array called inDegree to hold the in-degrees. After computing the in-degrees of each vertex, we add the vertices with in-degree 0 to the queue. Next, we take a vertex from the queue, remove all edges going out from that vertex, and update the in-degrees. If the size of the result list is not equal to the number of vertices, it indicates that a cycle exists, so we print -1.

Complexity Analysis

The time complexity of topological sorting is O(N + M), where N is the number of vertices and M is the number of edges. It takes O(M) time to count the in-degrees, and updating the in-degrees for each vertex also takes O(M). Therefore, the overall time complexity is O(N + M). The space complexity is O(N + M), considering the list to store the graph and the in-degree array.

Additional Practice Problems

Deepen your understanding and application of topological sorting through the following additional practice problems.

1. Create various combinations of tasks based on the given tasks and apply topological sorting.
2. Implement appropriate error handling when given a graph that contains cycles.
3. If there are multiple vertices with the same in-degree, implement it so that one of the vertices is randomly selected.

Conclusion

In this post, we learned about the concept and implementation of topological sorting, as well as how to apply it through an example problem. Topological sorting is an algorithm that is widely used in various fields, so it is important to understand it well and practice sufficiently.

Now you should feel confident using topological sorting to organize and manage complex tasks. Keep practicing and solving various problems!