C++ Coding Test Course, Understanding Trees

Author: Blog Author | Date: October 1, 2023

1. Problem Description

In this tutorial, we will learn about the tree data structure, which frequently appears in C++ coding tests, and solve algorithm problems using it.

The given problem is as follows:

Problem: Finding the Minimum and Maximum in a Binary Search Tree

Problem Description: Given a binary search tree (BST), write a program to find and output the minimum and maximum values of that tree.

A binary search tree has the following properties:

All nodes in the left subtree are less than the current node.
All nodes in the right subtree are greater than the current node.

The tree provided as input is in the following format:

The output should print the minimum and maximum values in order, and in the above example, the output would be:

            1
            8

Understanding binary search trees is essential to solve problems like this.

2. Insights into Binary Search Trees (BST)

A binary search tree (BST) is a data structure where each node contains data, and there are two child nodes (left and right). The left child node is always less than its parent node, and the right child node is always greater than its parent node.

Thanks to this property, using binary search trees allows for data searching, insertion, and deletion in O(log n) time.

The minimum value is found at the leftmost node of the left subtree.
The maximum value is found at the rightmost node of the right subtree.

When the depth of the tree is n, it is very efficient because you only need to traverse the tree to find the minimum and maximum values.

3. Algorithm Design

To find the minimum and maximum, we can define two functions. Each function explores the tree using either a recursive or iterative method.

            // Node structure definition for binary search tree
            struct Node {
                int data;
                Node* left;
                Node* right;
                
                Node(int val) : data(val), left(nullptr), right(nullptr) {}
            };

            // Function to find the minimum value
            Node* findMin(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->left == nullptr) return root;
                return findMin(root->left);
            }

            // Function to find the maximum value
            Node* findMax(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->right == nullptr) return root;
                return findMax(root->right);
            }

Each function provides a method to find the minimum or maximum by continuously moving left or right from the provided node.

4. C++ Code Implementation

The complete code for obtaining the minimum and maximum values in a binary search tree is as follows:

            #include 
            using namespace std;

            // Node structure definition for binary search tree
            struct Node {
                int data;
                Node* left;
                Node* right;

                Node(int val) : data(val), left(nullptr), right(nullptr) {}
            };

            // Function to find the minimum value
            Node* findMin(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->left == nullptr) return root;
                return findMin(root->left);
            }

            // Function to find the maximum value
            Node* findMax(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->right == nullptr) return root;
                return findMax(root->right);
            }

            int main() {
                // Sample tree creation
                Node* root = new Node(5);
                root->left = new Node(3);
                root->right = new Node(7);
                root->left->left = new Node(1);
                root->left->right = new Node(4);
                root->right->right = new Node(8);
                
                Node* minNode = findMin(root);
                Node* maxNode = findMax(root);

                if (minNode) cout << "Minimum value: " << minNode->data << endl;
                if (maxNode) cout << "Maximum value: " << maxNode->data << endl;

                // Freeing dynamically allocated memory
                delete root->left->left;
                delete root->left->right;
                delete root->left;
                delete root->right->right;
                delete root->right;
                delete root;

                return 0;
            }

Running the above code will output the minimum and maximum values of the given binary search tree.

5. Code Explanation

Let’s explain the main components of the program:

Node Structure: This structure defines each node that comprises the binary search tree. Each node contains an integer data and two child pointers (left and right).
findMin Function: This function follows the left child nodes from the given node to find the minimum value node. If there is no left child, that node is the minimum value.
findMax Function: This function follows the right child nodes from the given node to find the maximum value node. If there is no right child, that node is the maximum value.
main Function: This function creates a sample tree, calls each function to find the minimum and maximum values, prints the results, and then frees the dynamically allocated memory.

6. Conclusion

In this tutorial, we examined an algorithm to find the minimum and maximum values using C++’s binary search tree. The binary search tree is a highly efficient data structure with various applications. A deeper understanding of tree structures will aid in solving other tree-related problems.

In future lessons, we will prepare for more complex tree problems and algorithms that utilize trees. Stay tuned for the next tutorial!