Q2# Write the all four type of traversal sequence for this binary search tree?

Q2# Write the all four type of traversal sequence for this binary search tree?

Here are four types of traversal

Basically here are two types of traversal Algorthim

1. Breadth first Search (BFS)

BFS stands for Breadth-First Search. It is a graph traversal algorithm that explores all the vertices or nodes of a graph in breadthward motion, i.e., visiting all the vertices at the same level before moving to the next level. Here we have given values

Let us arrange values in graph

100

20

200

10

30

150

300

Rules:

1. it follows Queue Algorithms

2. Extract /explore.

3. Easy to get out put soon

100

20 200

10 30 150 300

Green denotes explores.

Yellow extracted.

STEP#1

100

20

200

STEP#2

20

200

10

30

STEP#3

200

10

30

150

300

STEP#4

10

30

150

300

STEP#5

30

150

300

STEP#6

150

300

STEP#7

300

2.Depth first Search

It is a graph traversal algorithm that explores as far as possible along each branch before backtracking. DFS visits vertices in a graph or nodes in a tree in a depth ward motion until it reaches a leaf node or a node with no unvisited neighbors. It is categorized further in 3 types

1. Inorder Traversal

2. Preorder Traversal

3. Postorder Traversa

1. Inorder Traversal:

• In inorder traversal, we visit the left subtree, then the root, and finally the right subtree.

• For a binary search tree, the inorder traversal visits the nodes in ascending order.

• In general, inorder traversal is commonly used to retrieve the elements of a binary tree in a sorted manner.

• Like

• Left

• Root

• Right

• Iteration = IT

100

STEP#1 STEP#7

STEP6

20 200

STEP#5

STEP#2 STEP#8 STEP#9

STEP4

STEP#3

10 30 150 300

>ITS USE 9 ITRATION FOR ACHIEVING THIS

2. Preorder Traversal:

• In preorder traversal, we visit the root, then the left subtree, and finally the right subtree.

• Preorder traversal is useful for creating a copy of the tree, as the root node is visited first.

• It is also used to serialize a binary tree into a string or to evaluate prefix expressions.

3. Postorder Traversal

• In postorder traversal, we visit the left subtree, then the right subtree, and finally the root.

• Postorder traversal is commonly used in deleting or freeing nodes of a binary tree.

• It is also useful in evaluating postfix expressions or obtaining a reversed version of the tree. Like:

Q3# Write the procedure ( pseudocode) for postorder tree traversal technique?

function postorderTraversal(node):

if node is null:

return

Traverse the left subtree

postorderTraversal(node.left)

Traverse the right subtree

postorderTraversal(node.right)

Visit the current node

visit(node)

Explanation:

The function postorderTraversal takes a node as input and performs a postorder traversal on the tree rooted at that node.

First, we check if the node is null. If it is, we simply return since there's nothing to traverse.

Otherwise, we recursively call postorderTraversal on the left subtree of the current node.

Next, we recursively call postorderTraversal on the right subtree of the current node.

Finally, we visit (process or print) the current node.

To use this pseudocode, you need to define the visit function according to your specific requirements. It represents the action you want to perform on each node during the traversal, such as printing the node's value or storing it in a data structure.