Binary Search Tree Program
Binary Search Tree Program
A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root. In this article , we will cover all the basics of binary search tree.
Reprsentation Of BST:
- The representation of a BST is similar to that of a binary tree. The order of a BST is ‘2’. Each node can have at most two children.
- Only difference between the two is that there is a certain criteria of arrangement or insertion of the elements based on their comparisons with the root node and the sub tree segment they are added to.
Operations In A BST:
- Traversal
- Searching
- Insertion
- Deletion
Features Of A BST:
- Fast look-up.
- Efficient addition and removal of items.
- Used to implement dynamic set of items
Code For Binary Search Tree
Run
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *create_node (int data)
{
struct node *new_node = (struct node *) malloc (sizeof (struct node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
struct node *insert_node (struct node *root, int data)
{
if (root == NULL)
{
return create_node (data);
}
if (data < root->data)
{
root->left = insert_node (root->left, data);
}
else
{
root->right = insert_node (root->right, data);
}
return root;
}
struct node *search_node (struct node *root, int data)
{
if (root == NULL || root->data == data)
{
return root;
}
if (data < root->data)
{
return search_node (root->left, data);
}
else
{
return search_node (root->right, data);
}
}
void inorder (struct node *root)
{
if (root != NULL)
{
inorder_traversal (root->left);
printf ("%d ", root->data);
inorder_traversal (root->right);
}
}
int main ()
{
struct node *root = NULL;
root = insert_node (root, 50);
insert_node (root, 30);
insert_node (root, 20);
insert_node (root, 40);
insert_node (root, 70);
insert_node (root, 60);
insert_node (root, 80);
inorder (root);
return 0;
}
Output :
20 30 40 50 60 70 80
Advantages Of BST:
- Inorder Traversal gives sorted order of elements.
- Easy to implement order statistics.
- Helpful in range queries.
Disadvantages Of BST:
- The cost of operations may be high.
- Shape of tree depends on insetions and may be degenerated.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment