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 = n8
pre_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