Draw the binary search tree that is created if the following numbers are inserted in the tree in the given order. (Pair of your registration number along with your age and any three number of your choice except present number for example: Regd No. is 2025, age 22 and three numbers are 50 25 62 then write [20 25 22 50 25 and 62]). Tree should be implemented using Link List.
Also write the pre-order, post-order and in-order traversal for the constructed binary search tree.
Answers
Answer:
Binary Search Tree | Set 1 (Search and Insertion)
The following is the definition of Binary Search Tree(BST) according to Wikipedia
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
There must be no duplicate nodes.
200px-Binary_search_tree.svg
The above properties of Binary Search Tree provides an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search for a given key.Searching a key
For searching a value, if we had a sorted array we could have performed a binary search. Let’s say we want to search a number in the array what we do in binary search is we first define the complete list as our search space, the number can exist only within the search space. Now we compare the number to be searched or the element to be searched with the mid element of the search space or the median and if the record being searched is lesser we go searching in the left half else we go searching in the right half, in case of equality we have found the element. In binary search we start with ‘n’ elements in search space and then if the mid element is not the element that we are looking for, we reduce the search space to ‘n/2’ and we go on reducing the search space till we either find the record that we are looking for or we get to only one element in search space and be done with this whole reduction.
Search operation in binary search tree will be very similar. Let’s say we want to search for the number, what we’ll do is we’ll start at the root, and then we will compare the value to be searched with the value of the root if it’s equal we are done with the search if it’s lesser we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are lesser and all the elements in the right subtree are greater. Searching an element in the binary search tree is basically this traversal in which at each step we will gInsertion of a key
A new key is always inserted at the leaf. We start searching a key from the root until 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++
// 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, i