# Tree traversal algorithm in Python

Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. - Wikipedia

Tree traversal algorithms can be classified in the following two categories:

- Depth-First Search (DFS): It starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
- Breadth-First Search (BFS): It starts at the tree’s root (selecting some arbitrary node as the root node in the case of a graph) and searches all nodes at the current depth level before moving on to the nodes at the next depth level.

Depth-First Search (DFS) algorithms have three variants:

- Preorder Traversal (current-left-right): Visit the current node before visiting any nodes inside left or right subtrees.
- Inorder Traversal (left-current-right): Visit the current node after visiting all nodes inside left subtree but before visiting any node within the right subtree.
- Postorder Traversal (left-right-current): Visit the current node after visiting all the nodes of left and right subtrees.

Breadth-First Search (BFS) Algorithm has one variant:

Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at the same level.

class Node:

def**init**(self, val):

self.val = val

self.left = None

self.right = None

def pre_order_traverse(node):

if node == None:

return

print(f”{node.val} “, end=””)

pre_order_traverse(node.left)

pre_order_traverse(node.right)

def in_order_traverse(node):

if node == None:

return

in_order_traverse(node.left)

print(f”{node.val} “, end=””)

in_order_traverse(node.right)

def post_order_traverse(node):

if node == None:

return

post_order_traverse(node.left)

post_order_traverse(node.right)

print(f”{node.val} “, end=””)

def level_order_traverse(node):

if node == None:

return

queue = []

queue.append(node)

while len(queue) > 0:

first = queue.pop(0)

print(f”{first.val} “, end=””)

if first.left != None:

queue.append(first.left)

if first.right != None:

queue.append(first.right)

root = Node(0)

n1 = Node(1)

n2 = Node(2)

root.left = n1

root.right = n2

n3 = Node(3)

n4 = Node(4)

n1.left = n3

n1.right = n4

n5 = Node(5)

n6 = Node(6)

n2.left = n5

n2.right = n6

n7 = Node(7)

n8 = Node(8)

n3.left = n7

n3.right = n8pre_order_traverse(root)

print()

in_order_traverse(root)

print()

post_order_traverse(root)

print()

level_order_traverse(root)

print()# Output:

# 0 1 3 7 8 4 2 5 6

# 7 3 8 1 4 0 5 2 6

# 7 8 3 4 1 5 6 2 0

# 0 1 2 3 4 5 6 7 8