Write a program in C fro Binary Search tree using following functions
1. Insertion operation using recursion
2. Deletion operation
3. Minimum/Maximum of a BST
6. Reorganize the tree so that the tree height is minimum
7. Print all the nodes from the node to the path to the root
8. Find the lowest common shared node between two given nodes
All functionality implemented without no. 6
if its not running on your machine(because of un-availability of some library run on
https://www.onlinegdb.com/online_c++_compiler#
code
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
struct node *left, *right;
int data;
};
void printPathsRecur(struct node* node, int path[], int
pathLen);
void printArray(int ints[], int len);
//A function that create nee node
struct node *newNode(int item)
{
struct node *temp = (struct node
*)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// get inorder traversal
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
cout<<"
"<<root->data;
inorder(root->right);
}
}
/* insert new node using recursion */
struct node* insert(struct node* node, int data)
{
/* If the node is empty, return a new node
*/
if (node == NULL) return newNode(data);
/* Otherwise, call Recursive */
if (data < node->data)
node->left =
insert(node->left, data);
else
node->right =
insert(node->right, data);
/* return node */
return node;
}
struct node * minValueNode(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current =
current->left;
return current;
}
/* Given a binary search tree and a data, this function deletes the
data
and returns the new root */
struct node* deleteNode(struct node* root, int data)
{
// base case
if (root == NULL) return root;
// If the data to be deleted is smaller than the
root's data,
// then it lies in left subtree
if (data < root->data)
root->left =
deleteNode(root->left, data);
// If the data to be deleted is greater than the
root's data,
// then it lies in right subtree
else if (data > root->data)
root->right =
deleteNode(root->right, data);
// if data is same as root's data, then This is
the node
// to be deleted
else
{
// node with only one
child or no child
if (root->left ==
NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right
== NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two
children: Get the inorder successor (smallest
// in the right
subtree)
struct node* temp =
minValueNode(root->right);
// Copy the inorder
successor's content to this node
root->data =
temp->data;
// Delete the inorder
successor
root->right =
deleteNode(root->right, temp->data);
}
return root;
}
// find min value
int minValue(struct node* node) {
struct node* curr = node;
while (curr->left != NULL) {
curr = curr->left;
}
return(curr->data);
}
// find max value
int maxValue(struct node* node)
{
/* loop down to find the rightmost leaf */
struct node* current = node;
while (current->right != NULL)
current =
current->right;
return (current->data);
}
// check is leaf node or not
bool isLeaf(struct node* node)
{
return (node->left == nullptr &&
node->right == nullptr);
}
// Print path from leaf to root
void printPath(vector<int> const &path)
{
for (int k = path.size() - 1; k > 0; k--)
cout << path.at(k) << "
-> ";
cout << path.at(0) << endl;
}
void LeafToRootPaths(struct node* node, vector<int>
&path)
{
if (node == nullptr)
return;
path.push_back(node->data);
if (isLeaf(node))
printPath(path);
LeafToRootPaths(node->left, path);
LeafToRootPaths(node->right, path);
// remove current node after left and right subtree
are done
path.pop_back();
}
// print all paths from leaf to root node
void LeafToRootPaths(struct node* node)
{
vector<int> path;
// recursive function
LeafToRootPaths(node, path);
}
bool findPath(struct node *root, vector<int> &Path,
int j)
{
// base case
if (root == NULL) return false;
// Store this node in path vector. The node will
be removed if
// not in path from root to k
Path.push_back(root->data);
// See if the k is same as root's data
if (root->data == j)
return true;
// Check if k is found in left or right
sub-tree
if ( (root->left &&
findPath(root->left, Path, j)) ||
(root->right
&& findPath(root->right, Path, j)) )
return true;
Path.pop_back();
return false;
}
int findLCA(struct node *root, int l1, int l2)
{
// to store paths to n1 and n2 from the
root
vector<int> path1, path2;
if ( !findPath(root, path1, l1) ||
!findPath(root, path2, l2))
return
-1;
/* paths to get the first different value
*/
int k;
for (k = 0; k < path1.size() && k
< path2.size() ; k++)
if (path1[k] !=
path2[k])
break;
return path1[k-1];
}
// main function
int main()
{
cout<<"Inserting node in tree \n";
struct node *root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout<<"After inserting node Inorder
traversal of the given tree is \n";
inorder(root);
cout<<"\n Deleting node\n";
cout<<"\nDelete 50\n";
root = deleteNode(root, 50);
cout<<"\n Inorder traversal of the
modified (Deleted 50) tree \n";
inorder(root);
cout<<"\n Minimum value Tree is "<<
minValue(root);
cout<<"\n Maximum value in Tree is
"<< maxValue(root);
cout<<"\n Getting all path from leaf to
root";
cout<<"\n path is \n";
LeafToRootPaths(root);
cout<<"Lowest common shared node between
two given nodes (20,40)";
cout << "nLCA(20, 40) = " << findLCA(root, 20,
40);
return 0;
}
/*
output
Inserting node in tree
After inserting node Inorder traversal of the given tree is
20 30 40 50 60 70 80
Deleting node
Delete 50
Inorder traversal of the modified (Deleted 50) tree
20 30 40 60 70 80
Minimum value in BST is 20
Maximum value in BST is 80
getting all path from leaf to root
path is
20 -> 30 -> 60
40 -> 30 -> 60
80 -> 70 -> 60
Lowest common shared node between two given nodes (20,40)nLCA(20, 40) = 30
*/
Write a program in C fro Binary Search tree using following functions 1. Insertion operation using...
Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate insert operation in binary search tree. Please fill in the missing part for the insert method to make the program work. The expected output should be as follows. 20 30 40 50 60 70 80 Part B: Find Lowest Common Ancestor (LCA) of a Binary Search Tree. According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and...
Binary Search tree Implementation of a BST class that include the following operations: - Insertion, Search, Deletion - Traversals: Inorder, Preorder, Postorder using c++
Insert the following values in the given order into a Binary Search Tree and use the resulting BST in the next 5 questions. 15 8 3 6 23 9 11 10 20 13 5 9. What is the height of the resulting Binary Search Tree? 10. What is the depth of the node that stores the value 11? 11. Is there a path from the node storing the value 15 to the node storing the value 5? If so, show...
In this assignment, you will add several methods to the Binary Search Tree. You should have completed the following three methods in the lab: public void insert(Key key, Value value) public Value get(Key key) public void inorder(Node root) For this assignment, you will implement the following: public void remove(Node root, Key key) public Key getMin(Node n) public Key getMax(Node n) public int height(Node n) The main method contains the statements to check whether your implementation works. You need to change...
Construct a Binary Search Tree (BST) program in C++. The program is required to: 1) load the BST from a dataset (I will provide the datasets-see below) in the order they exist in the dataset. 2) after the BST is built analyze the BST and display the following values: 2.1) the smallest branch height 2.2) the highest branch height 2.3) the number of nodes in the tree 2.4) the determination if the tree is balanced 2.5) the determination if the...
Recall that in a binary search tree, at every node, all elements to the left of the node have a smaller key, and all elements to the right of a node have a larger key. Write a program called that takes two parameters: a pointer to a binary search tree node, and an int parameter called min which will print all the elements bigger than the specified value, min. Your program should allow the user to enter data (integer) from...
Using C Please comment
Part 1: BST Create a link based Binary Search tree composed of a Node and a Tree struct. You should have a header file, BST.h, with the following: o Node struct containing left, right, and parent pointers, in addition to holding an Data struct value Tree struct containing a pointer to the root of the tree A function declaration for a function that allocates a tree, and initializes the root to NULL o o o A...
Data structures C++1- A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1 Out of the following choices, which is the minimum set of nodes, if removed, will make the BST balanced?2- Which of the following is true for Red-Black Trees ? Select all choices that apply! Select one or more: a. For each node in the tree, all paths from that node to any leaf nodes contain...
Write a C program to build a complete binary tree with 7 nodes using link list implementation. Requirements: 1) Ask the user to enter randomly seven integer numbers as data value for each node 2) Build the tree using link list 3) Print the tree in inorder , preorder , and post order 4) Use functions for each print type .