Algorithms Explained #6: Tree Traversal | by Claudia Ng | Oct, 2022
Explanation of tree traversal algorithms with examples in Python
Trees are represented by a set of nodes connected by edges. They are considered a hierarchical and non-linear data structure, because data in a tree is stored on multiple levels. Trees have the following properties:
- Root node: every tree has one node designated as the root node, which is the node at the top of the tree and is the node that does not have any parent nodes.
- Parent node: a parent node is the node preceding it, and every node except the root node has one parent node.
- Child node: a child node is the node after it. Depending on the type of tree, every node can have a varying numbers of child nodes.
There are general trees that have the properties listed above and no other restrictions on number of nodes. There are also various types of tree data structures with more restrictions for different use cases and below are some commonly seen ones:
- Binary tree: A binary tree is one where nodes can have at most two child nodes each, as the “binary” label suggests.
- Binary search tree (BST): A BST is a special case of a binary tree where the nodes are ordered by their values. For every parent node, the left child node is a smaller value, while the right child node is a larger value. This structure makes lookups fast and hence useful for searching and sorting algorithms.
- Heaps: A heap is a special tree data structure and there are two types of heaps: i) a Min Heap is a tree structure where each parent node is less than or equal to its child node; ii) a Max Heap is a tree structure where each parent node is greater than or equal to its child node. This type of data structure is useful for implementing priority queues where items are prioritized by weightage. Note that Python has a built-in library called
heapqwith functions to perform different operations on a heap data structure.
After reviewing the common types of tree data structures, below are some common examples of tree traversal algorithms and their implementation in Python.
Breadth-first Search (BFS)
Bread-first search (BFS) is a common algorithm used to traverse a binary search tree (BST) or graph in a systematic order. It starts at the root node at level 0 and visits nodes one at a time moving laterally from one side to the other until the desired node is found or all nodes have been visited. The algorithm searches wide first before going deeper, hence the name bread-first search.
The time complexity of BFS is O(n), because the tree size is dictated by the item search length and each node is visited once. Below is the implementation in Python:
def bfs(graph, source):
"""Function to traverse graph/ tree using breadth-first search Parameters:
graph (dict): dictionary with node as key and
list of connected nodes as values.
source (str): source node to start from, usually
the root node of the tree. Returns:
bfs_result (list): list of visited nodes in order.
"""
# Define variables
bfs_result = []
queue = [] # Add source node to queue
queue.append(source) while queue:
# Visit node at front of queue
node = queue.pop(0) # Check if we have visited this node before
if node not in bfs_result:
# Mark node as visited
bfs_result.append(node)
# Add all neighbor nodes to queue
for neighbor in graph.get(node, []):
queue.append(neighbor) return bfs_result
Depth-first Search
Depth-first search (DFS) is another variation of a tree traversal algorithm where it also starts at the root node but travels down a branch and goes as far down a branch as it can. If the desired node is not in that branch, it comes back up and selects another branch to go down. The algorithm does this until the desired node is found or all nodes have been visited. The algorithm explores down a branch (deep) first before going to another branch, hence the name depth-first search.
The time complexity of DFS is also O(n) for the same reasons as BFS. Below is the implementation in Python:
def dfs(graph, source):
"""Function to traverse graph/ tree using depth-first search Parameters:
graph (dict): dictionary with node as key and
list of child nodes as values.
source (str): source node to start from, usually
the root node of the tree. Returns:
dfs_result (list): list of visited nodes in order.
"""
# Define variables
dfs_result = []
queue = [] # Add source node to queue
queue.append(source) while queue:
# Get last item in queue
node = queue.pop() # Check if we have visited node before
if node not in dfs_result:
dfs_result.append(node)
# Add neighbors to queue
for neighbor in graph.get(node, []):
queue.append(neighbor) return dfs_result
Conclusion
Trees are useful data structures for representing hierarchical and non-linear data. The most commonly used types of tree data structures are binary tree (each node in tree has at most two child nodes), binary search tree (binary tree where nodes are ordered by values), and heaps (tree where parent nodes are less than or more than their child nodes depending on whether it is a min heap or max heap).
In terms of algorithms, bread-first search and depth-first search are important tree traversal algorithms with many real-world applications, ranging from path finding and route planning in GPS navigation systems to scheduling to network topology. In the next article, we will go through a special example of a tree traversal used for information encoding called the Huffman Code.
See more from this Algorithms Explained series: #1: recursion, #2: sorting, #3: search, #4: greedy algorithms, #5: dynamic programming, #6: tree traversal (current article).
Explanation of tree traversal algorithms with examples in Python
Trees are represented by a set of nodes connected by edges. They are considered a hierarchical and non-linear data structure, because data in a tree is stored on multiple levels. Trees have the following properties:
- Root node: every tree has one node designated as the root node, which is the node at the top of the tree and is the node that does not have any parent nodes.
- Parent node: a parent node is the node preceding it, and every node except the root node has one parent node.
- Child node: a child node is the node after it. Depending on the type of tree, every node can have a varying numbers of child nodes.
There are general trees that have the properties listed above and no other restrictions on number of nodes. There are also various types of tree data structures with more restrictions for different use cases and below are some commonly seen ones:
- Binary tree: A binary tree is one where nodes can have at most two child nodes each, as the “binary” label suggests.
- Binary search tree (BST): A BST is a special case of a binary tree where the nodes are ordered by their values. For every parent node, the left child node is a smaller value, while the right child node is a larger value. This structure makes lookups fast and hence useful for searching and sorting algorithms.
- Heaps: A heap is a special tree data structure and there are two types of heaps: i) a Min Heap is a tree structure where each parent node is less than or equal to its child node; ii) a Max Heap is a tree structure where each parent node is greater than or equal to its child node. This type of data structure is useful for implementing priority queues where items are prioritized by weightage. Note that Python has a built-in library called
heapqwith functions to perform different operations on a heap data structure.
After reviewing the common types of tree data structures, below are some common examples of tree traversal algorithms and their implementation in Python.
Breadth-first Search (BFS)
Bread-first search (BFS) is a common algorithm used to traverse a binary search tree (BST) or graph in a systematic order. It starts at the root node at level 0 and visits nodes one at a time moving laterally from one side to the other until the desired node is found or all nodes have been visited. The algorithm searches wide first before going deeper, hence the name bread-first search.
The time complexity of BFS is O(n), because the tree size is dictated by the item search length and each node is visited once. Below is the implementation in Python:
def bfs(graph, source):
"""Function to traverse graph/ tree using breadth-first search Parameters:
graph (dict): dictionary with node as key and
list of connected nodes as values.
source (str): source node to start from, usually
the root node of the tree. Returns:
bfs_result (list): list of visited nodes in order.
"""
# Define variables
bfs_result = []
queue = [] # Add source node to queue
queue.append(source) while queue:
# Visit node at front of queue
node = queue.pop(0) # Check if we have visited this node before
if node not in bfs_result:
# Mark node as visited
bfs_result.append(node)
# Add all neighbor nodes to queue
for neighbor in graph.get(node, []):
queue.append(neighbor) return bfs_result
Depth-first Search
Depth-first search (DFS) is another variation of a tree traversal algorithm where it also starts at the root node but travels down a branch and goes as far down a branch as it can. If the desired node is not in that branch, it comes back up and selects another branch to go down. The algorithm does this until the desired node is found or all nodes have been visited. The algorithm explores down a branch (deep) first before going to another branch, hence the name depth-first search.
The time complexity of DFS is also O(n) for the same reasons as BFS. Below is the implementation in Python:
def dfs(graph, source):
"""Function to traverse graph/ tree using depth-first search Parameters:
graph (dict): dictionary with node as key and
list of child nodes as values.
source (str): source node to start from, usually
the root node of the tree. Returns:
dfs_result (list): list of visited nodes in order.
"""
# Define variables
dfs_result = []
queue = [] # Add source node to queue
queue.append(source) while queue:
# Get last item in queue
node = queue.pop() # Check if we have visited node before
if node not in dfs_result:
dfs_result.append(node)
# Add neighbors to queue
for neighbor in graph.get(node, []):
queue.append(neighbor) return dfs_result
Conclusion
Trees are useful data structures for representing hierarchical and non-linear data. The most commonly used types of tree data structures are binary tree (each node in tree has at most two child nodes), binary search tree (binary tree where nodes are ordered by values), and heaps (tree where parent nodes are less than or more than their child nodes depending on whether it is a min heap or max heap).
In terms of algorithms, bread-first search and depth-first search are important tree traversal algorithms with many real-world applications, ranging from path finding and route planning in GPS navigation systems to scheduling to network topology. In the next article, we will go through a special example of a tree traversal used for information encoding called the Huffman Code.
See more from this Algorithms Explained series: #1: recursion, #2: sorting, #3: search, #4: greedy algorithms, #5: dynamic programming, #6: tree traversal (current article).
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.