KEMBAR78
BST Struct | PDF | Computer Programming | Software Engineering
Scribd
Upload
37 views3 pages

BST Struct

The document defines a Node struct to represent nodes in a binary search tree (BST) and a BST class to implement operations on the tree such as insertion, removal, finding minimum/maximum elements, and traversal. The main function demonstrates using the BST by inserting elements, printing the inorder traversal, finding min/max, removing an element, and printing the updated traversal.

Uploaded by

Barath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
37 views3 pages

BST Struct

The document defines a Node struct to represent nodes in a binary search tree (BST) and a BST class to implement operations on the tree such as insertion, removal, finding minimum/maximum elements, and traversal. The main function demonstrates using the BST by inserting elements, printing the inorder traversal, finding min/max, removing an element, and printing the updated traversal.

Uploaded by

Barath
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

#include <iostream>

using namespace std;

struct Node {
int key;
Node* left;
Node* right;

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


};

struct BST {
Node* root;

BST() : root(nullptr) {}

Node* insert(Node* node, int key) {


if (node == nullptr)
return new Node(key);

if (key < node->key)


node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

return node;
}

Node* findMin(Node* node) {


while (node->left != nullptr)
node = node->left;
return node;
}

Node* findMax(Node* node) {


while (node->right != nullptr)
node = node->right;
return node;
}

Node* remove(Node* node, int key) {


if (node == nullptr)
return node;

if (key < node->key)


node->left = remove(node->left, key);
else if (key > node->key)
node->right = remove(node->right, key);
else {
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp;
}
Node* temp = findMin(node->right);
node->key = temp->key;
node->right = remove(node->right, temp->key);
}
return node;
}

void inorderTraversal(Node* node) {


if (node == nullptr)
return;

inorderTraversal(node->left);
cout << node->key << " ";
inorderTraversal(node->right);
}

void insert(int key) {


root = insert(root, key);
}

void remove(int key) {


root = remove(root, key);
}

int findMin() {
if (root == nullptr)
return -1; // or any appropriate error code
Node* minNode = findMin(root);
return minNode->key;
}

int findMax() {
if (root == nullptr)
return -1; // or any appropriate error code
Node* maxNode = findMax(root);
return maxNode->key;
}

void inorder() {
inorderTraversal(root);
cout << endl;
}
};

int main() {
BST bst;
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);

cout << "Inorder traversal: ";


bst.inorder();

cout << "Minimum value: " << bst.findMin() << endl;


cout << "Maximum value: " << bst.findMax() << endl;
bst.remove(30);
cout << "Inorder traversal after deleting 30: ";
bst.inorder();

return 0;
}

You might also like