logo
  • Home
  • Rank
  • Tests
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C Program to Search for an Element in a Binary Search Tree

Posted on April 19, 2014 by cguy3
This C program searches an element in a Binary Search Tree.

In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node based binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right sub-tree. Each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node. Average search time complexity for BST is O(logn).

Here is the source code of the C program to search for an element in a Binary Search Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. struct node
  4. {
  5.     int info;
  6. 	struct node*left;
  7. 	struct node*right;
  8. };
  9. typedef struct node BST;
  10. BST *LOC, *PAR;
  11. void search(BST *root, int item)
  12. {
  13.     BST *save,*ptr;
  14.     if (root == NULL)
  15.     {
  16.         LOC = NULL;
  17.         PAR=NULL;
  18.     }
  19.     if (item == root -> info)
  20.     {
  21.     LOC = root;
  22.     PAR = NULL;
  23.     return;
  24.     }
  25.     if (item < root->info)
  26.     {
  27.         save = root;
  28.         ptr = root->left;
  29.     }
  30.     else
  31.     {
  32.         save = root;
  33.         ptr = root -> right;
  34.     }
  35.     while( ptr != NULL)
  36.     {
  37.         if (ptr -> info == item)
  38.         {
  39.             LOC = ptr;
  40.             PAR = save;
  41.             return;
  42.         }
  43.         if(item < ptr->info)
  44.         {
  45.             save = ptr;
  46.             ptr = ptr->left;
  47.         }
  48.         else
  49.         {
  50.             save = ptr;
  51.             ptr = ptr->right;
  52.         }
  53.     }
  54.     LOC = NULL;
  55.     PAR = save;
  56.     return;
  57. }
  58.  
  59. struct node* findmin(struct node*r)
  60. {
  61. 	if (r == NULL)
  62. 		return NULL;
  63. 	else if (r->left!=NULL)
  64. 		return findmin(r->left);
  65. 	else if (r->left == NULL)
  66. 		return r;
  67. }
  68. struct node*insert(struct node*r, int x)
  69. {
  70. 	if (r == NULL)
  71. 	{
  72.             r = (struct node*)malloc(sizeof(struct node));
  73.             r->info = x;
  74.             r->left = r->right = NULL;
  75.             return r;
  76. 	}
  77. 	else if (x < r->info)
  78.             r->left = insert(r->left, x);
  79. 	else if (x > r->info)
  80.             r->right = insert(r->right, x);
  81. 	return r;
  82. }
  83.  
  84. struct node* del(struct node*r, int x)
  85. {
  86. 	struct node *t;
  87. 	if(r == NULL)
  88. 		printf("\nElement not found");
  89. 	else if (x < r->info)
  90.             r->left = del(r->left, x);
  91. 	else if (x > r->info)
  92.             r->right = del(r->right, x);
  93. 	else if ((r->left != NULL) && (r->right != NULL))
  94. 	{
  95.             t = findmin(r->right);
  96.             r->info = t->info;
  97.             r->right = del(r->right, r->info);
  98. 	}
  99. 	else
  100. 	{
  101.             t = r;
  102.             if (r->left == NULL)
  103.                 r = r->right;
  104.             else if (r->right == NULL)
  105.                 r = r->left;
  106.             free(t);
  107. 	}
  108. 	return r;
  109. }
  110.  
  111.  
  112. int main()
  113. {
  114.     struct node* root = NULL;
  115.     int x, c = 1, z;
  116.     int element;
  117.     char ch;
  118.     printf("\nEnter an element: ");
  119.     scanf("%d", &x);
  120.     root = insert(root, x);
  121.     printf("\nDo you want to enter another element :y or n");
  122.     scanf(" %c",&ch);
  123.     while (ch == 'y')
  124.     {
  125.         printf("\nEnter an element:");
  126.         scanf("%d", &x);
  127.         root = insert(root,x);
  128.         printf("\nPress y or n to insert another element: y or n: ");
  129.         scanf(" %c", &ch);
  130.     }
  131.     while(1)
  132.     {
  133.         printf("\n1 Insert an element ");
  134.         printf("\n2 Delete an element");
  135.         printf("\n3 Search for an element ");
  136.         printf("\n4 Exit ");
  137.         printf("\nEnter your choice: ");
  138.         scanf("%d", &c);
  139.         switch(c)
  140.         {
  141.             case 1:
  142.                 printf("\nEnter the item:");
  143.                 scanf("%d", &z);
  144.                 root = insert(root,z);
  145.                 break;
  146.             case 2:
  147.                 printf("\nEnter the info to be deleted:");
  148.                 scanf("%d", &z);
  149.                 root = del(root, z);
  150. 		break;
  151.             case 3:
  152.                 printf("\nEnter element to be searched:  ");
  153.                 scanf("%d", &element);
  154.                 search(root, element);
  155.                 if(LOC != NULL)
  156.                     printf("\n%d Found in Binary Search Tree !!\n",element);
  157.                 else
  158.                     printf("\nIt is not present in Binary Search Tree\n");
  159.                 break;
  160.             case 4:
  161.                 printf("\nExiting...");
  162. 		return;
  163.             default:
  164.                 printf("Enter a valid choice: ");
  165.  
  166.         }
  167.     }
  168.     return 0;
  169. }

$ gcc bst.c -o bst
$ ./bst
 
Enter an element: 32
Do you want to enter another element, y or n: y
Enter an element: 54
Press y or n to insert another element, y or n: y
Enter an element: 65
Press y or n to insert another element, y or n: y
1 Insert an element 
2 Delete an element
3 Search for an element 
4 Exit 
Enter your choice: 3
Enter element to be searched:  32
32 Found in Binary Search Tree !!
 
1 Insert an element 
2 Delete an element
3 Search for an element 
4 Exit 
Enter your choice: 4
Exiting...

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.

« Prev Page - C Program to Perform the Shaker Sort
» Next Page - Program to Perform Searching Using Self-Organizing Lists

« C++ Program For Inorder Tree Traversal without Recursion
C++ Program to Find the Number of Permutations of a Given String »

Deep Dive @ Sanfoundry:

  1. Java Programming Examples on Combinatorial Problems & Algorithms
  2. C Programming Examples on Combinatorial Problems & Algorithms
  3. Java Programming Examples on Graph Problems & Algorithms
  4. C++ Programming Examples on Graph Problems & Algorithms
  5. C Programming Examples on Graph Problems & Algorithms
  6. C Programming Examples using Recursion
  7. C# Programming Examples on Data Structures
  8. C Programming Examples on Linked List
  9. C Programming Examples without using Recursion
  10. C Programming Examples on Trees
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below:
LinkedIn | Facebook | Twitter | Google+

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.