Tree Traversal in DSA
Tree traversal involves travelling over each node in a tree Data Structure in order. Navigating a tree is crucial in scenarios like looking through every record for a certain activity, even if finding, adding, and removing nodes are often used activities. O(N) is the total time complexity for going through a tree with N items.
A number of popular tree traversal techniques can be broadly divided into depth-first and breadth-first strategies.
Depth-First Traversals
First-Depth Traversals Before turning around, depth-first traversals go as far as they can along each branch. Usually, a stack or recursive implementation are used for these traversals.
Preorder Traversal: Preorder traversals visit the root node first, then its left and right subtrees. This arrangement may help transform algebraic equations into prefix notation or generate a tree-structured document’s table of contents.
Logic:
- Visit the the node that is currently in use.
- Go over the left subtree recursively.
- Go over the right subtree recursively.
Example:
Illustrates how the preorder technique creates places in presale. It iteratively invokes the subtree preorder non-public utility method. This code calls itself recursively on its children after returning the current node p.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def preorder_traversal(root):
if root:
print(root.value, end=" ")
preorder_traversal(root.left)
preorder_traversal(root.right)
# Tree structure:
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Preorder Traversal:")
preorder_traversal(root)Output:
Preorder Traversal:
1 2 4 5 3 Inorder Traversal: Traversal of Inorder The left subtree is visited first, followed by the current node and the right subtree in an inorder traverse. Because it explores each node in ascending order of its key values, an in-order traversal is very important for binary search trees. Because of this, it can be used to create a sorted list of data from a tree.
Logic:
- Go over the left subtree recursively.
- Go to the node that is currently in use.
- Go over the right subtree recursively.
Example:
This is illustrated by the private recursive version of the inOrde rTraverse method. A public inOrderTraverse method calls this. Stack-based non-recursive generator versions are also offered.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.value, end=" ")
inorder_traversal(root.right)
# Example Tree Structure:
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Inorder Traversal:")
inorder_traversal(root)Output:
Inorder Traversal:
4 2 5 1 3 Postorder Traversal: Traversal of Postorder In a postorder traversal, the current node is visited after recursively going through the left and right subtrees. Applications like evaluating arithmetic equations written in postfix notation benefit from this sequence. Additionally, it is representative of calculations such as disc space calculation, in which the total space of a directory is determined by the space occupied by its child directories.
Logic:
- Go over the left subtree recursively.
- Go over the right subtree recursively.
- Go to the node that is currently in use.
Example:
Postorder makes use of the same subtree postorder utility as preorder.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.value, end=" ")
# Example Tree Structure:
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Postorder Traversal:")
postorder_traversal(root)Output:
Postorder Traversal:
4 5 2 3 1Breadth-First Traversal (BFS)
Breadth-First Traversal (BFS) Before going on to nodes at the next deeper level, a breadth-first traversal, in contrast to depth-first traversals, explores every node at a specific depth (level). The order of node visits is usually managed by a queue in this non-recursive method, which guarantees “first-in, first-out” (FIFO) processing. In terms of the number of edges, a path from a beginning vertex to any other vertex in a BFS tree is always the shortest path.
Logic (Queue-based):
- Enqueue the root node and initialise a queue.
- Dequeue a node while the queue is not empty. b. Go to the node that was dequeued. c. Enqueue all of the dequeued node’s unvisited children.
Example:
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def level_order_traversal(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.value, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Example Tree Structure:
# 1
# / \
# 2 3
# / \
# 4 5
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Level Order Traversal (Queue-based):")
level_order_traversal(root)Output:
Level Order Traversal (Queue-based):
1 2 3 4 5 Depth-First Search (DFS) for Graphs
Depth-First Search (DFS) for Graphs The phrase “Depth-First Search” (DFS) is most frequently used to refer to graph traversal, but preorder, inorder, and postorder are distinct kinds of depth-first traversals for trees. DFS methodically investigates a graph by going as far as it can down each branch before turning around. It tracks which vertices need to be visited implicitly using a stack.
It is helpful for identifying pathways, detecting cycles in graphs, and verifying connectedness. Edges, including “back edges” in undirected graphs, can be categorised as “discovery edges” (going to new vertices) or “nontree edges” (leading to vertices that have already been visited).
Euler Tour Traversal Framework
Traversal Framework for the Euler Tour Based on the idea of a “walk” around a tree, the Euler tour traversal offers a more general framework for constructing tree traversals. With the edges always on the left, this walk begins at the root and moves precisely twice along each edge once up and once down. O(N) is its complexity.
The “template method pattern,” which defines a general computation mechanism that may be tailored for particular applications, is used in the Euler tour. It makes use of “hooks” auxiliary functions that subclasses can override to specify specialised behaviour at specific traversal steps. There are two primary hooks.
- hook previsit(p, d, path): This function is called before to navigating subtrees; it serves as the “pre visit” when a position is initially reached.
- Hook postvisit(p, d, path, results): Refers to the “post visit” while moving upward from a location and is called after subtrees are traversed.
It is possible to insert an extra hook for binary trees called hook invisit, which is invoked after the left subtree has been traversed but before the right subtree.
Example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def euler_tour(root, path=[]):
if root:
# On entering the node (Preorder visit)
path.append(f"Enter {root.value}")
euler_tour(root.left, path)
# After traversing the left subtree (Inorder visit)
path.append(f"Visit {root.value}")
euler_tour(root.right, path)
# After traversing the right subtree (Postorder visit)
path.append(f"Leave {root.value}")
return path
# example tree:
# 1
# / \
# 2 3
root = Node(1)
root.left = Node(2)
root.right = Node(3)
# Perform Euler Tour Traversal
print("Euler Tour Traversal:")
tour = euler_tour(root)
print("\n".join(tour))Output:
Euler Tour Traversal:
Enter 1
Enter 2
Visit 2
Leave 2
Visit 1
Enter 3
Visit 3
Leave 3
Leave 1These hook methods can then be overridden by subclasses to provide particular traversal behaviours, like determining disc space, printing indented tables of contents, or parenthetic representations.