BFS in Complete Tree

 BFS in Complete Tree

 The breadth-first search or BFS algorithm is used to search a tree or graph data structure for a node that meets a set of criteria. It begins at the root of the tree or graph and investigates all nodes at the current depth level before moving on to nodes at the next depth level.

 

• Completeness: Yes, BFS is complete for traversing all nodes in a tree or a graph.

• Time Complexity: For a tree with $n$ nodes and $m$ edges, the time complexity of BFS is $O(n+m)$. In the case of a tree where $m=n-1$.
  

• Space Complexity: The space complexity of BFS is $O(w)$, where $w$ is the maximum width or the maximum number of nodes at any level in the tree.

• Optimality: Yes, BFS is optimal for finding the shortest path in an unweighted graph or tree since it explores nodes level by level.

Tree:  

 

 Code:

 class Node:

def __init__(self, value):

self.data = value

self.left = None

self.right = None

def Insert(root, val):

if root is None:

return Node(val)

queue = [root]

while queue:

current = queue.pop(0)

if current.left is None:

current.left = Node(val)

return

elif current.right is None:

current.right = Node(val)

return

else:

queue.append(current.left)

queue.append(current.right)

def Inorder(root):

if root:

Inorder(root.left)

print(root.data, end=" ")

Inorder(root.right)

def BFS(root):

if root is None:

return None

queue = [root]

while queue:

current = queue.pop(0)

print(current.data, end=" ")

if current.left:

queue.append(current.left)

if current.right:

queue.append(current.right)

root = Node(1)

Insert(root, 2)

Insert(root, 3)

Insert(root, 4)

Insert(root, 5)

Insert(root, 6)

Insert(root, 7)

print(end="Inorder: ")

Inorder(root)

print()

print(end="BFS: ")

BFS(root)

print()

 Explanation:

 

 Sample input and output:

 

 

....Thank you....