Notes

Program to implement search in BST

// C function to search a given key in a given BST

#include <stdio.h>
#include <stdlib.h>

struct node {
int key;
struct node *left, *right;
};

// A utility function to create a new BST node
struct node* newNode(int item)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to insert a new node with given key in BST
struct node* insert(struct node* node, int key)
{ // If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

// Return the (unchanged) node pointer
return node;
}

// Utility function to search a key in a BST
struct node* search(struct node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}





// Driver Code
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// Key to be found
int key = 6;
// Searching in a BST
if (search(root, key) == NULL)
printf("%d not foundn", key);
else
printf("%d foundn", key);

key = 60;
// Searching in a BST
if (search(root, key) == NULL)
printf("%d not foundn", key);
else
printf("%d foundn", key);
return 0;
}

Output
6 not found
60 found

Time complexity: O(h), where h is the height of the BST.

Auxiliary Space: O(h), where h is the height of the BST. This is because the maximum amount of space needed to store the recursion stack would be h.


 
Insert a node in Binary Search Tree using Iteration

struct node* newNode(int item)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to insert a new Node with given key in BST
struct node* insert(struct node* root, int key)
{
// Create a new Node containing the new element
struct node* nnode = newNode(key);

// Pointer to start traversing from root and traverses downward //path to search where the new node to be inserted
Node* ptr = root;

// Pointer pptr maintains the trailing pointer of ptr
Node* pptr = NULL;

while (ptr != NULL)
{
pptr = ptr;
if (key < ptr ->key)
ptr = ptr ->left;
else
ptr = ptr ->right;
}

// If the root is NULL i.e the tree is empty The new node //is the root node
if (pptr == NULL)
pptr = nnode;

// If the new key is less than the leaf node key Assign //the new node to be its left child
else if (key < pptr ->key)
pptr ->left = nnode;
// else assign the new node its right child
else
pptr ->right = nnode;
// Returns the pointer where the new node is inserted
return pptr;
}

 

int iterativeSearch(struct Node* root, int key)
{ // Traverse until root reaches to dead end
while (root != NULL)
{
// pass right subtree as new tree
if (key > root->data)
root = root->right;
// pass left subtree as new tree
else if (key < root->data)
root = root->left;
else
return 1; // if the key is found return 1
}
return 0;
}