Question

Write a program to allow user to create a binary search tree. Your program should display in BFT and DFT(in order) format.

Answer #1

**Illustration to search 6 in below tree:**

1. Start from root.

2. Compare the inserting element with root, if less than root, then
recurse for left, else recurse for right.

3. If element to search is found anywhere, return true, else return
false.

**Insertion of a key**

A new key is always inserted at leaf. We start searching a key from
root till we hit a leaf node. Once a leaf node is found, the new
node is added as a child of the leaf node.

100 100 / \ Insert 40 / \ 20 500 ---------> 20 500 / \ / \ 10 30 10 30 \ 40

```
// C++ program to demonstrate insertion
// in a BST recursively.
#include <iostream>
using namespace std;
class BST
{
int data;
BST *left, *right;
public:
// Default constructor.
BST();
// Parameterized constructor.
BST(int);
// Insert function.
BST* Insert(BST *, int);
// Inorder traversal.
void Inorder(BST *);
};
// Default Constructor definition.
BST :: BST() : data(0), left(NULL), right(NULL){}
// Parameterized Constructor definition.
BST :: BST(int value)
{
data = value;
left = right = NULL;
}
// Insert function definition.
BST* BST :: Insert(BST *root, int value)
{
if(!root)
{
// Insert the first node, if root is NULL.
return new BST(value);
}
// Insert data.
if(value > root->data)
{
// Insert right node data, if the 'value'
// to be inserted is greater than 'root' node data.
// Process right nodes.
root->right = Insert(root->right, value);
}
else
{
// Insert left node data, if the 'value'
// to be inserted is greater than 'root' node data.
// Process left nodes.
root->left = Insert(root->left, value);
}
// Return 'root' node, after insertion.
return root;
}
// Inorder traversal function.
// This gives data in sorted order.
void BST :: Inorder(BST *root)
{
if(!root)
{
return;
}
Inorder(root->left);
cout << root->data << endl;
Inorder(root->right);
}
// Driver code
int main()
{
BST b, *root = NULL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);
b.Inorder(root);
return 0;
}
```

BFT:

**Algorithm:**

For each node, first the node is visited and then it’s child nodes
are put in a FIFO queue.

printLevelorder(tree) 1) Create an empty queue q 2) temp_node = root /*start from root*/ 3) Loop while temp_node is not NULL a) print temp_node->data. b) Enqueue temp_node’s children (first left then right children) to q c) Dequeue a node from q and assign it’s value to temp_node

**Implementation:**

Here is a simple implementation of the above algorithm. Queue is
implemented using an array with maximum size of 500. We can
implement queue as linked list also.

```
/* C++ program to print level order traversal using STL */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// Iterative method to find height of Binary Tree
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;
// Create an empty queue for level order traversal
queue<Node *> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false)
{
// Print front of queue and remove it from queue
Node *node = q.front();
cout << node->data << " ";
q.pop();
/* Enqueue left child */
if (node->left != NULL)
q.push(node->left);
/*Enqueue right child */
if (node->right != NULL)
q.push(node->right);
}
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "Level Order traversal of binary tree is \n";
printLevelOrder(root);
return 0;
}
```

**Output:**

Level order traversal of binary tree is - 1 2 3 4 5

Binary Search Tree Code in Java
Write a program that prompts user to enter however many numbers
they want to add to the binary search tree. Then have the user
input numbers until the tree contains that many elements. If the
user enters a number that already exists in the tree, then a
message should be displayed "Number is already in the tree". Once
all elements are added to the tree print its contents in sorted
order.
Assume all user...

Write a C++ program that checks whether a binary search tree is
an AVL. The input is an arbitrary binary search tree, and the
output is binary, so either true or false.

In this lab, you will write a program that creates a binary
search tree based on user input. Then, the user will indicate what
order to print the values in. **Please write in C code**
Start with the bst.h and bst.c base code provided to you. You
will need to modify the source and header file to complete this
lab.
bst.h:
#ifndef BST_H
#define BST_H
typedef struct BSTNode
{
int value;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
BSTNode*...

Given the list of values below, create a Binary Search Tree for
the list, Use the first value in the list as the root of the tree,
add the nodes to BST in the order they appear in the list.[50, 44,
82, 39, 35, 98, 87, 100, 74, 23, 34, 14, 94]
What is the minimum height of a Binary Tree that contains
24nodes?
What is the minimum height of a Binary Tree that contains
64nodes?
What is the minimum...

a) Design a recursive linear-time algorithm that tests whether a
binary tree is a binary search tree. Describe your algorithm in
English or with a simple pseudocode program. b) (3 bonus pts.)
Extend the algorithm in a) to test whether a binary tree is an AVL
tree.

JAVA
Write a program that has two functions in which the user chooses
which one to perform;
1. reads in a CSV file of integers into an array and insert it
into a binary search tree class
2. deserializes an object and inserts it into a binary search
tree class
the tree class must be in a separate class from the CSV file
read and deserialize object load

This program is in C++:
Write a program to allow the user to:
1. Create two classes. Employee and Departments.
The Department class will have: DepartmentID, Departmentname,
DepartmentHeadName.
The Employee class will have employeeID, emploeename,
employeesalary, employeeage, employeeDepartmentID.
Both of the above classes should have appropriate constructors,
accessor methods.
2. Create two arrays . One for Employee with the size 5 and
another one for Department with the size 3.
Your program should display a menu for the user to...

What is the output of the Euler tour in the normal binary
search tree if the key insert order is 5 , 2 , 8 , 5 , 9 , 5 , 1 ,
3 , 4 , 2 , 8 ? All keys equal to the node should be the right
subtree of that node.
____________________________________________________________
Construct the binary max - heap for the keys given below. Once
all the keys are inserted, perform the remove maximum operation,
and...

Design a program that asks user to enter any three numbers. The
program should display the three numbers in ascending order. using
python code please

Write a program that asks the user for the name of a file.
The program should display only the first five lines of the
file’s contents.
If the file contains less than five lines, it should display the
file’s entire contents. by python using while
loop

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 9 minutes ago

asked 12 minutes ago

asked 20 minutes ago

asked 30 minutes ago

asked 30 minutes ago

asked 33 minutes ago

asked 43 minutes ago

asked 47 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago