full implementation of binary search tree in C++
Full Implementation of Binary Search Tree in C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
class BST {
private:
Node* root;
Node insertRecursive(Node root, int value) {
if (root == nullptr) {
Node* newNode = new Node();
newNode->data = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
if (value < root->data) {
root->left = insertRecursive(root->left, value);
} else {
root->right = insertRecursive(root->right, value);
}
return root;
}
void inOrderTraversal(Node* root) {
if (root != nullptr) {
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
}
public:
BST() : root(nullptr) {}
void insert(int value) {
root = insertRecursive(root, value);
}
void inOrder() {
inOrderTraversal(root);
cout << endl;
}
};
Explanation:
- The code defines a structure Node
to represent each node in the binary search tree (BST).
- A class BST
is defined to encapsulate the BST functionality.
- The private section of the class contains the root
pointer and helper functions for insertion and traversal.
- The insertRecursive
function is a helper function to insert a new value into the BST recursively.
- The inOrderTraversal
function performs in-order traversal of the BST, printing the nodes in ascending order.
- The public section of the class provides methods to insert values into the BST and perform in-order traversal.
- The insert
method calls the insertRecursive
function to insert a new value into the BST.
- The inOrder
method calls the inOrderTraversal
function to perform in-order traversal of the BST and print the values.