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(node):
# We'll collect the result in a list to return it
# instead of printing directly inside the recursive function
# This makes the function more reusable.
result = []
_preorder_recursive(node, result)
return result
def _preorder_recursive(node, result_list):
if node:
result_list.append(node.value)
_preorder_recursive(node.left, result_list)
_preorder_recursive(node.right, result_list)
# Create tree
# A
# / \
# B C
# / \ \
# D E F
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.right.right = Node('F')
# Preorder traversal
print("Preorder traversal:")
output = preorder_traversal(root)
print(output)
# Example with an empty tree
print("\nPreorder traversal (empty tree):")
empty_root = None
empty_output = preorder_traversal(empty_root)
print(empty_output)
# Example with a single node tree
print("\nPreorder traversal (single node):")
single_root = Node('X')
single_output = preorder_traversal(single_root)
print(single_output)Output:
Preorder traversal:
['A', 'B', 'D', 'E', 'C', 'F']
Preorder traversal (empty tree):
[]
Preorder traversal (single node):
['X']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(node):
"""
Performs an inorder traversal of the binary tree.
Returns a list of node values in inorder sequence.
"""
result = []
_inorder_recursive(node, result)
return result
def _inorder_recursive(node, result_list):
"""
Helper function for recursive inorder traversal.
"""
if node:
_inorder_recursive(node.left, result_list)
result_list.append(node.value)
_inorder_recursive(node.right, result_list)
# Create a sample tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
# Perform Inorder traversal
print("Inorder Traversal:")
output = inorder_traversal(root)
print(output)
# Example with a different tree (using characters for variety)
# M
# / \
# P Q
# / \
# R S
root2 = Node('M')
root2.left = Node('P')
root2.right = Node('Q')
root2.left.left = Node('R')
root2.right.right = Node('S')
print("\nInorder Traversal (another tree):")
output2 = inorder_traversal(root2)
print(output2)
# Example with an empty tree
print("\nInorder Traversal (empty tree):")
empty_root = None
empty_output = inorder_traversal(empty_root)
print(empty_output)
# Example with a single node tree
print("\nInorder Traversal (single node):")
single_root = Node(100)
single_output = inorder_traversal(single_root)
print(single_output)Output:
Inorder Traversal:
[4, 2, 5, 1, 3, 6]
Inorder Traversal (another tree):
['R', 'P', 'M', 'Q', 'S']
Inorder Traversal (empty tree):
[]
Inorder Traversal (single node):
[100]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(node):
"""
Performs a postorder traversal of the binary tree.
Returns a list of node values in postorder sequence.
"""
result = []
_postorder_recursive(node, result)
return result
def _postorder_recursive(node, result_list):
"""
Helper function for recursive postorder traversal.
"""
if node:
_postorder_recursive(node.left, result_list)
_postorder_recursive(node.right, result_list)
result_list.append(node.value)
# Create a sample tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
# Perform Postorder traversal
print("Postorder Traversal:")
output = postorder_traversal(root)
print(output)
# Example with a different tree (using characters for variety)
# G
# / \
# H I
# / \
# J K
root2 = Node('G')
root2.left = Node('H')
root2.right = Node('I')
root2.left.left = Node('J')
root2.right.right = Node('K')
print("\nPostorder Traversal (another tree):")
output2 = postorder_traversal(root2)
print(output2)
# Example with an empty tree
print("\nPostorder Traversal (empty tree):")
empty_root = None
empty_output = postorder_traversal(empty_root)
print(empty_output)
# Example with a single node tree
print("\nPostorder Traversal (single node):")
single_root = Node(99)
single_output = postorder_traversal(single_root)
print(single_output)Output:
Postorder Traversal:
[4, 5, 2, 6, 3, 1]
Postorder Traversal (another tree):
['J', 'H', 'K', 'I', 'G']
Postorder Traversal (empty tree):
[]
Postorder Traversal (single node):
[99]Breadth-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])
result = []
while queue:
current = queue.popleft()
result.append(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return result
# Build a sample tree:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)
# Perform level-order traversal and print the output
output = level_order_traversal(root)
print("Level-order traversal:", output)
# Another example: A single node tree
root_single = Node(10)
output_single = level_order_traversal(root_single)
print("Level-order traversal (single node):", output_single)
# Another example: An empty tree
root_empty = None
output_empty = level_order_traversal(root_empty)
print("Level-order traversal (empty tree):", output_empty)Output:
Level-order traversal: [1, 2, 3, 4, 5, 6]
Level-order traversal (single node): [10]
Level-order traversal (empty tree): []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(node, path=None, indent=""):
"""
Performs an Euler Tour traversal of the binary tree.
This version collects the tour steps into a list.
"""
if path is None:
path = []
if node:
path.append(f"Enter {node.value}")
# print(f"{indent}Enter {node.value}")
if node.left:
euler_tour(node.left, path, indent + " ")
path.append(f"Visit {node.value}")
# print(f"{indent}Visit {node.value}")
if node.right:
euler_tour(node.right, path, indent + " ")
path.append(f"Leave {node.value}")
# print(f"{indent}Leave {node.value}")
return path
# Create a sample tree:
# A
# / \
# B C
# / \
# D E
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
# Perform Euler Tour
print("Euler Tour Traversal:")
tour_path = euler_tour(root)
# Print each step on a new line for better readability
for step in tour_path:
print(step)
# Example with a simpler tree:
# P
# /
# Q
print("\nEuler Tour Traversal (simpler tree):")
root_simple = Node('P')
root_simple.left = Node('Q')
tour_path_simple = euler_tour(root_simple)
for step in tour_path_simple:
print(step)
# Example with an empty tree:
print("\nEuler Tour Traversal (empty tree):")
empty_root = None
empty_tour = euler_tour(empty_root)
print(empty_tour if empty_tour else "No tour for an empty tree.")
# Example with a single node tree:
print("\nEuler Tour Traversal (single node):")
single_root = Node('X')
single_tour = euler_tour(single_root)
for step in single_tour:
print(step)Output:
Euler Tour Traversal:
Enter A
Enter B
Enter D
Visit D
Leave D
Visit B
Enter E
Visit E
Leave E
Leave B
Visit A
Enter C
Visit C
Leave C
Leave A
Euler Tour Traversal (simpler tree):
Enter P
Enter Q
Visit Q
Leave Q
Visit P
Leave P
Euler Tour Traversal (empty tree):
No tour for an empty tree.
Euler Tour Traversal (single node):
Enter X
Visit X
Leave XThese 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.