[go: up one dir, main page]
Scribd
Upload
4 views9 pages

PRE - Order - Traversal BST

The document provides a C program for implementing a Binary Search Tree (BST) with operations for inserting elements and performing a preorder traversal. It includes a step-by-step algorithm detailing the structure of the BST, the functions for creating nodes, inserting values, and traversing the tree. Additionally, it explains the concept of a binary search tree and the preorder traversal method.

Uploaded by

shubhambhusanpandey
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views9 pages

PRE - Order - Traversal BST

The document provides a C program for implementing a Binary Search Tree (BST) with operations for inserting elements and performing a preorder traversal. It includes a step-by-step algorithm detailing the structure of the BST, the functions for creating nodes, inserting values, and traversing the tree. Additionally, it explains the concept of a binary search tree and the preorder traversal method.

Uploaded by

shubhambhusanpandey
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

CODE

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

typedef struct Node {


int data;
struct Node* left;
struct Node* right;
} Node;

Node* createNode(int data);


Node* insert( Node* root, int data);
void preorderTraversal(Node* root);

int main()
{
Node* root = NULL;
int choice, value;

printf("Binary Search Tree Operations:\n");

do {
printf("\n1. Insert element\n");
printf("2. Preorder Traversal\n");
printf("0. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
break;
case 0:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 0);
return 0;
}
Node* createNode(int data) {
Node* newNode = ( Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

Node* insert( Node* root, int data) {


if (root == NULL) {
return createNode(data);
}

if (data < root->data) {


root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}

return root;
}

void preorderTraversal( Node* root) {


if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
Algorithm

✅ Step-by-Step Algorithm for BST Operations

Step 1: Start the program

Step 2: Define the structure Node


 Each node contains:
o Integer data
o Pointer left (to left child)
o Pointer right (to right child)

Step 3: Define function createNode(data)


 Allocate memory for a new node
 Set node->data = data
 Set node->left = NULL
 Set node->right = NULL
 Return the new node

Step 4: Define function insert(root, data)


 If root is NULL, create and return a new node with given
data
 If data < root->data, recursively insert into the left
subtree
 If data > root->data, recursively insert into the right
subtree
 Return root

Step 5: Define function preorderTraversal(root)


 If root is not NULL:
o Print root->data
o Recursively call preorderTraversal(root->left)
o Recursively call preorderTraversal(root->right)

Step 6: In the main() function


1. Initialize root to NULL
2. Declare choice and value variables

Step 7: Display menu in a loop


 Repeat the following steps until the user enters 0:
a. Print the menu:
1. Insert element
2. Preorder Traversal
0. Exit
b. Ask the user to enter choice
c. Use switch(choice) to handle options:
 Case 1 (Insert):
o Prompt user to enter a value
o Call insert(root, value) to insert value into the BST
o Update root with the returned node
 Case 2 (Preorder Traversal):
o Call preorderTraversal(root) to print BST in pre-
order
 Case 0 (Exit):
o Print exit message
o End loop
 Default case:
o Print "Invalid choice" message

Step 8: End the program

WHAT IS A BINARY SEARCH TREE?


A binary tree is a hierarchical data structure in which each
node has at most two children, referred to as the left child
and the right child. It starts with a root node, and each node
can recursively act as the root of its own subtree. Binary trees
are used to represent sorted data, expressions, decision-
making processes, and more. There are different types like
full, complete, perfect, and binary search trees (BST). They
support various traversal methods such as in-order, pre-
order, and post-order. Binary trees are widely used in
computer science for efficient searching and sorting
operations.
✅ 1. Binary Search Tree (BST)
A binary tree where:
 Left child < Root < Right child
 All left descendants are less than the node
 All right descendants are greater
Example:
10
/ \
5 15
/\ \
2 7 20
Used in: Searching, insertion, and deletion operations in
O(log n) time (average case).
Pre-order Traversal of a Binary Tree

🔹 Definition:
Pre-order traversal is a type of depth-first traversal where
the nodes are visited in the following order:
Root → Left → Right
This means:
1. Visit the current node (root)
2. Traverse the left subtree recursively
3. Traverse the right subtree recursively
🔹 Steps:
Given a binary tree:
mathematica
Copy code
A
/\
B C
/\ \
D E F
🔹 Pre-order Traversal:
 Start at root A → print A
 Move to left child B → print B
 Move to B's left child D → print D
 Back to B, move to right child E → print E
 Back to root A, move to right child C → print C
 Move to C's right child F → print F
🔹 Output:
ABDECF

You might also like