Problem 1017 BST-Create a binary search tree (BST) and output its in-order seque

Question

Problem 1017 BST-Create a binary search tree (BST) and output its in-order sequence Middle level) 1: Introduction Problem description and (f any) background of the algorithms. Description BST,,BST, ,BST, BST,:,BST (FindMinFindMax) Create a binary search tree (BST) based on the input data by insertion operation, and output the first-order traversal sequence of it. If possible, please also output the minimal element and the maximal element by calling functions Find Min and FindMax, respectively Tips: use insertion operation to create a BST Input: , N, N. (100Ne-10000) We can input many groups of data, where for each group of data inputted in wo lines, First line: the number of elements in the BST tree; Second line: pre-order sequence of the EST; the minimal element and the maximal element Output: , BST BST () Fist line: the number of different elements in the BST Second line: The pre-order Third line: the minimal element and the maximal element (not required in sequence of the BST the website) Sample Input 12 23 324812 Sample Output 2 48 23 32 4 32 2: Algorithm Specification Description (pseudo-code preferred) of all the algorithms involved for solving the problem, including specifications of main data structures. 3: Testing Results Table of test cases. Each test case usnally consists of a brief description of the purpose of this case, the expected result, the actual behavior of your program, the possible cause of a bug if your program does not function as expected, and the current status pass", or "corrected. or "pending") 4: Analysis and Comments Analysis of the time and space complexities of the algorithms. Comments on further possible improvements. Appendix: Source Code (in CiC++)

Explanation / Answer

1. main.cpp

#include<iostream>
using namespace std;

class node //class for a node of a tree
{
public:
int data; //number stored in the node
node*left; // pointer to left node
node*right; //pointer to right node

node(int d) //constructor for the node
{
data=d;
left=NULL;
right=NULL;
}
};

node* insertInBST(node*root,int data) //Function for inserting an element in BST
{
if(root==NULL) //if root is NULL then we add the node here
{
root = new node(data);
return root;
}
if(data <= root->data) //if data<root->data then we go in the left subtree
{
root->left = insertInBST(root->left,data);
}
else //if data>root->data then we go in the right subtree
{
root->right = insertInBST(root->right,data);
}
return root;
}

void takeInput(node*&root, int n) //helper function for insertInBST
{
int d; //for storing data entered by user
while(n--) // Takes input n times
{
cin>>d; //Takes an element from user
root = insertInBST(root,d); //calls insertInBST for inserting this number in BST
}
}
void printPreorder(node*root) //function for printing preorder traversal of BST
{
if(root==NULL){
return;
}
cout<<root->data<<" "; //data of root is printed
printPreorder(root->left); //then we go to left subtree
printPreorder(root->right); // and then we go to right subtree

}
int findMin(node *root) //function for finding minimal element
{

while(root->left!=NULL) //As the minimum element in BST is the leftmost element
{
root= root->left;
}
return root->data;
}
int findMax(node *root) //function for finding maximal element
{

while(root->right!=NULL) //As the maximum element in BST is the rightmost element
{
root= root->right;
}
return root->data;
}
int main()
{
node*root = NULL;
int n; //for storing no of elements
cout<<"Enter no of elements: ";
cin>>n; //taking n from user
cout<<"Enter the elements: ";
takeInput(root,n); //inserting elements in BST
printPreorder(root); //printing preorder traversal of BST
cout<<endl<<findMin(root)<<" "; //Displaying minimum element
cout<<findMax(root); //Displaying maximum element
return 0;
}

2. In BST, the left subtree of a node contains only nodes with keys lesser than the node’s key and the right subtree of a node contains only nodes with keys greater than the node’s key. These properties are applied to every node. So, the minimum element is situated in the leftmost node and the maximum element is stored in the rightmost mode. These properties of BST are used to solve the problem.

3. The program is working as expected.

4. Time complexity for insertion of one element is equal to the height of the tree.

Also, for finding maximum and minimum element, time complexity is equal to the height of the tree.

Space complexity is O(1) as there is no extra space used.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.