Operation On Binary Search Tree(BST)

 Operation On Binary Search Tree(BST)

1. Create:- Create tree with 'n' nodes.
2. Traverse:- Visit each & every node of tree.
3. Search:- Searches for a specific element in the tree.
4.  Insert:- The new element will be inserted according to its value.
5. Delete:- Delete a specific node from the tree.
6. Counting total nodes
7. Counting leaf nodes
8. Copying tree to another
9. Mirror of tree

• Create:-

        Some rules satisfy for create a nodes. 

1. All keys in the left subtree < root.
2. All keys in the right subtree >= root.
3. The right & left subtree are also Binary Search Tree(BST).

    

    Algorithm:-

    Step 1:- Start

    Step 2:- root=NULL

    Step 3:- Read the value and create a newnode to store this value.

    Step 4:- If root==NULL

                  root=newnode

                  goto Step 7

    Step 5:- temp=root

    Step 6:- If key<temp->info

                     If temp doesn't have left child

                           attach newnode to temp->left

                            go to Step 7

                     Else

                           temp=temp->left;

                            go to Step 7

                Else

                        IF temp doesn't have right child,

                            attach newnode to temp->right

                        Else

                             temp=temp->right

                              go to Step 6

    Step 7:- Repeat from 3 till all values have been inserted in tree.

    Step 8:- Stop

• Traverse

1. Traversing tree means visiting all it's nodes to get the complete tree tree information.
2. Data structure like array and linked list are linear. Hence it is easy to traverse all element.
3. A tree is a non linear data structure hence tree traversal is complicated.

Three methods to traverse tree:-

• Perorder(Data-Left-Right):-

1. Visit the root.
2. Traverse left subtree in Preorder.
3. Treverse right subtree in Preorder.

• Inorder(Left-Data-Right)

1. Traverse left subtree in Inorder.
2. Visit the root.
3. Treverse right subtree in Inorder.

• Postorder(Left-Right-Data)

1. Traverse left subtree in Postorder.
2. Treverse right subtree in Postorder. 
3. Visit the root.    

    Code:-

                  👇

1. #include<stdio.h>
2. #include<stdlib.h>
3. 
   
4. typedef struct node
5. {
6. int info;
7. struct node *left, *right;
8. }NODE;
9. 
   
10. //TREE FUNCTION
11. NODE * createbst(NODE *root)
12. {
13. NODE *newnode, *temp, *parent;
14. int i, n, num;
15. printf("\nHow many nodes you want to enter?\t");
16. scanf("%d", &n);
17. for(i=1; i<=n; i++)
18. {
19. newnode = (NODE*)malloc(sizeof (NODE));
20. printf("Enter the %d elements:\t", n);
21. scanf("%d", &num);
22. newnode->info=num;
23. newnode->left = newnode->right = NULL;
24. if(root == NULL)
25. {
26. root = newnode;
27. continue;
28. }
29. temp = root;
30. while(temp != NULL)
31. {
32. parent = temp;
33. if(num < temp->info)
34. temp = temp->left;
35. else
36. temp = temp->right;
37. }
38. if(num < parent->info)
39. parent->left = newnode;
40. else
41. parent->right = newnode;
42. }
43. return(root);
44. }
45.                    // Traversal Function
46. void preorder(NODE * root)
47. {
48. NODE *temp = root;
49. if(temp != NULL)
50. {
51. printf("%d\t", temp->info);
52. preorder(temp->left);
53. preorder(temp->right);
54. }
55. }
56. 
    
57. void inorder(NODE * root)
58. {
59. NODE *temp = root;
60. if(temp != NULL)
61. {
62. inorder(temp->left);
63. printf("%d\t", temp->info);
64. inorder(temp->right);
65. }
66. }
67. 
    
68. void postorder(NODE * root)
69. {
70. NODE *temp = root;
71. if(temp != NULL)
72. {
73. postorder(temp->left);
74. postorder(temp->right);
75. printf("%d\t", temp->info);
76. }
77. }
78. 
    
79. 
    
80. 
    
81. void main()
82. {
83. NODE *root=NULL;
84. printf("\t>>CREATE & TRAVERSAL<<\n");
86. root = createbst(root);
88. //Recursive Traversal
89. printf("\nPerorder traversal is:\t"); 
90. preorder(root);
92. printf("\nInorder traversal is:\t");
93. inorder(root);
95. printf("\nPostorder traversal is:\t");
96. postorder(root);
98. 
    
99. }

👉Execute👈

//OUTPUT

/*

>>CREATE & TRAVERSAL<<

How many nodes you want to enter? 5

Enter the 5 elements: 10

Enter the 5 elements: 5

Enter the 5 elements: 15

Enter the 5 elements: 6

Enter the 5 elements: 12

Perorder traversal is: 10 5 6 15 12

Inorder traversal is: 5 6 10 12 15

Postorder traversal is: 6 5 12 15 10

*/