b.stefanuk.ca

Appearance

Multiple ways to visit each node

  1. BFS
  2. DFS
    1. Preorder traversel
    2. postorder traversel
    3. inorder traversal

BFS ​

python
queue = # store the whole node in the queue, not just value
result = # just the values
loop {
	  # only for as long as the queue is not empty
	  # pop and append from/to queue
}
def BFS(node):
	current_node = node
	queue = [] # implemented as a list
	results = []
	append.append(current_node) # put this in the queue before while loop
	while len(queue) > 0:
		current_node = queue.pop(0)
		results.append(current_node.value)
		if current_node.left is not None:
			queue.append(current_node.left)
		if current_node.right is not None:
			queue.append(current_node.right)
	return results
queue = # store the whole node in the queue, not just value
result = # just the values
loop {
	  # only for as long as the queue is not empty
	  # pop and append from/to queue
}
def BFS(node):
	current_node = node
	queue = [] # implemented as a list
	results = []
	append.append(current_node) # put this in the queue before while loop
	while len(queue) > 0:
		current_node = queue.pop(0)
		results.append(current_node.value)
		if current_node.left is not None:
			queue.append(current_node.left)
		if current_node.right is not None:
			queue.append(current_node.right)
	return results

DFS Preorder ​

python
dfs_preorder(node)
	result = []
	def traverse(node):
		results.append(node.val)
		if node.left:
			traverse(node.left)
		if node.right:
			travese(node.right)
	traverse(node)
	return result
dfs_preorder(node)
	result = []
	def traverse(node):
		results.append(node.val)
		if node.left:
			traverse(node.left)
		if node.right:
			travese(node.right)
	traverse(node)
	return result

DFS Postorder ​

python
dfs_postorder(node)
	results = []
	def traverse(node)
		if node.left:
			traverse(node.left)
		if node.right:
			traverse(node.right)
		results.append(node.value)
	traverse(node)
	return results
dfs_postorder(node)
	results = []
	def traverse(node)
		if node.left:
			traverse(node.left)
		if node.right:
			traverse(node.right)
		results.append(node.value)
	traverse(node)
	return results

DFS Inorder ​

python
dfs_inorder(node)
	results = []
	def traverse(node)
		if node.left:
			traverse(node.left)
		results.append(node.value)
		if node.right:
			traverse(node.right)
	traverse(node)
	return results
dfs_inorder(node)
	results = []
	def traverse(node)
		if node.left:
			traverse(node.left)
		results.append(node.value)
		if node.right:
			traverse(node.right)
	traverse(node)
	return results

TODO: Add all the new ways you know how to write tree traversals