Python: BFS And DFS

BFS and DFS are two different ways you can traverse a Tree. BFS is Breadth First Search and DFS is Depth First Search.

To explain this further, consider the following tree:

You can see how BFS traversal works there. Also, you see there are three ways to do DFS traversal:

  • pre-order
  • in-order
  • and post-order.

Depth First Search

class BTnode:
 
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None
 
def DFS(node):
	#left
	if node.left:
		DFS(node.left)
	#right
	if node.right:
		DFS(node.right)
	#root
	print(node.value, end=' ') # no new line after print
 
b = BTnode(1)
b.left = BTnode(2)
b.right = BTnode(3)
b.left.left = BTnode(4)
b.left.right = BTnode(5)
b.right.left = BTnode(6)
b.right.right = BTnode(7)
 
DFS(b)
print() #manually adding new line after result

The order of left, right and root can be changed there to convert that into pre-order and in-order.

Breadth First Search

class Queue:
	def __init__(self):
		self.items = []
 
	def put(self, item):
		self.items.append(item)
 
	def get(self):
		if self.items:
			return self.items.pop(0)
 
	def isEmpty(self):
		return self.items == []
 
class BTnode:
 
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None
 
def BFS(node):
	q = Queue()
	q.put(node) #enqueue
 
	while not q.isEmpty():
		current = q.get() #dequeue
		print(current.value, end=' ') #prints without adding new line
 
		if current.left:
			q.put(current.left)
		if current.right:
			q.put(current.right)
 
b = BTnode(1)
b.left = BTnode(2)
b.right = BTnode(3)
b.left.left = BTnode(4)
b.left.right = BTnode(5)
b.right.left = BTnode(6)
b.right.right = BTnode(7)
 
BFS(b)
print() #manually adding new line after result

We’ve used a Queue there to implement BFS. Here’s how it works:

  1. Add 1
  2. Pop 1 and add it’s children 2 and 3
  3. Pop 2 and add it’s children 4 and 5
  4. Pop 3 and add it’s children 6 and 7
  5. Pop all other items (as none have children)

This is illustrated in the image below:

That’s all in this post! 🙂

Leave a comment